package com.zjw.algorithm;

import com.zjw.algorithm.utils.Utils;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。
 * <p>
 * 当你在格子 (i, j) 的时候，你可以移动到以下格子之一：
 * <p>
 * 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
 * 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。
 * 请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。
 * <p>
 * 简单来讲 只能向右或者向下移动，移动数小于等于所在位置网格权值
 * <p>
 * 提示：
 * <p>
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 105
 * 1 <= m * n <= 105
 * 0 <= grid[i][j] < m * n
 * grid[m - 1][n - 1] == 0
 */

public class Solution10 {

    public static void main(String[] args) {
        System.out.println(new Solution10().minimumVisitedCells(new int[][]{{3, 4, 2, 1}, {4, 2, 3, 1}, {2, 1, 0, 0}, {2, 4, 0, 0},}));
        System.out.println(new Solution10().minimumVisitedCells(new int[][]{{3, 4, 2, 1}, {4, 2, 1, 1}, {2, 1, 1, 0}, {3, 4, 1, 0},}));
        System.out.println(new Solution10().minimumVisitedCells(new int[][]{{2, 1, 0}, {1, 0, 0},}));
        System.out.println(new Solution10().minimumVisitedCells(new int[][]{{3, 12, 6, 13}, {1, 15, 1, 8}, {10, 19, 15, 7}, {4, 1, 2, 2}, {8, 12, 12, 0}}));


        String data = "[[0,4,0,2,4,1,1,3,1,2,1,1,0,3,2,2,0,0,3,2,2,2,0,2,3,3,2,0,3,1,0,0,3,3,3,0,3,1,3,1,3,1,2,2,1,3,2,3,2,2,2,1,2,3,2,3,2,2,3,0,2,3,1,0,1,0,3,0,1,2,3,1,0,3,1,0,1,1,0,0,2,3,3,2,1,0,2,2,0,1,2,2,0,1,1,1,2,1,2,2,2,0,1,1,1,2,1,0,0,1,0,2,2,1,0,1,1,0,0,1,2,0,1,0,0,2,0,0,2,2,0,2,1],[0,4,4,1,3,1,1,0,3,0,0,0,1,2,3,0,3,2,0,1,0,3,1,2,3,1,0,2,2,0,1,0,1,1,0,1,1,1,3,1,1,0,2,3,0,1,3,1,3,3,1,0,3,3,3,3,3,3,0,1,2,1,0,1,2,3,0,3,2,1,3,2,3,1,2,1,0,3,2,0,0,1,1,0,2,0,1,1,2,2,0,2,0,2,2,2,1,1,2,1,1,2,2,0,0,2,1,2,0,1,1,0,1,1,2,1,2,2,0,2,2,2,2,0,0,0,1,2,0,2,1,1,1],[1,3,0,4,1,3,2,0,1,0,0,2,0,1,2,1,2,2,1,3,0,0,3,1,2,1,3,1,2,3,2,3,2,2,3,0,3,3,1,0,0,2,0,1,2,3,3,1,1,1,0,0,0,0,0,2,1,0,1,1,1,1,2,3,1,1,0,0,0,2,2,0,2,0,3,3,3,3,0,2,3,3,2,0,1,2,1,2,0,0,1,1,2,1,1,0,0,0,1,1,2,2,1,2,2,2,2,2,2,2,2,1,2,0,0,0,2,2,0,0,0,1,1,2,0,0,2,1,1,2,0,1,0],[0,1,0,4,0,2,1,1,2,2,0,2,0,3,0,3,2,1,3,0,1,3,0,2,3,2,2,0,3,0,2,1,2,1,3,2,3,0,3,2,1,2,0,3,2,0,3,2,0,2,2,2,0,1,2,3,3,3,0,2,1,2,1,3,3,3,2,3,0,2,2,0,1,3,3,0,0,2,1,2,1,2,0,1,0,0,2,1,0,2,0,0,1,0,1,1,1,1,2,1,0,1,1,0,2,2,0,2,2,0,2,1,2,0,0,1,0,0,1,2,2,1,0,2,2,0,0,0,0,1,2,1,1],[3,2,4,2,2,2,3,3,1,0,1,3,2,0,3,0,1,1,1,2,3,3,2,2,2,0,2,2,2,2,0,1,2,1,1,0,2,2,2,3,0,2,3,2,1,3,0,3,2,3,1,3,1,3,0,1,0,3,2,2,2,3,2,1,2,3,1,1,2,1,2,3,2,2,0,1,2,2,3,3,0,1,2,1,2,1,1,2,0,0,1,1,2,0,0,2,1,2,1,0,2,0,2,2,1,1,1,0,2,2,1,1,0,1,0,0,2,2,1,2,2,0,1,0,1,1,1,1,2,1,1,1,0],[3,2,2,3,2,1,2,0,2,1,2,1,1,3,2,1,1,2,2,1,2,3,2,3,0,3,3,2,3,0,3,2,2,0,1,2,3,1,0,2,3,2,2,1,0,3,3,2,2,3,1,2,0,3,2,1,2,3,1,3,1,3,0,0,0,2,1,3,0,1,1,2,0,0,2,1,0,3,0,2,1,0,1,2,1,1,0,1,2,0,2,2,2,2,1,0,1,0,1,0,2,1,0,2,0,1,1,1,2,0,2,2,1,1,1,2,0,2,2,1,2,2,2,2,1,2,2,1,1,2,1,1,1],[2,3,1,3,0,0,3,1,2,1,0,2,2,2,1,2,3,0,1,3,0,2,2,2,3,2,3,3,2,2,0,3,1,2,0,3,2,0,2,2,1,3,2,1,0,3,0,1,2,1,1,1,0,0,0,0,2,0,3,0,2,1,3,2,3,3,2,1,3,3,0,1,1,1,1,3,0,3,0,0,1,2,2,1,1,0,1,1,1,1,0,1,2,0,1,2,0,2,0,0,0,0,0,1,0,0,0,1,1,1,2,1,2,0,2,0,1,1,1,0,2,2,0,0,2,1,0,0,1,0,2,2,0],[0,2,0,2,0,0,1,0,3,0,3,3,0,3,1,0,3,2,1,0,3,3,1,1,2,0,0,2,3,2,1,0,3,3,0,3,2,2,1,0,2,3,3,0,3,3,3,0,1,0,2,1,1,3,3,3,3,2,3,2,2,0,1,2,3,1,2,3,0,2,2,2,0,2,1,0,0,2,1,1,1,1,1,0,0,0,0,1,0,2,1,1,2,0,0,0,0,1,1,1,2,0,1,1,1,2,2,2,2,0,1,2,2,2,1,2,0,1,1,1,0,2,0,2,1,0,2,2,2,1,1,2,2],[1,1,2,0,0,1,1,3,2,3,3,1,2,0,0,0,2,3,2,0,0,2,0,1,1,3,3,0,2,0,1,0,3,1,1,1,1,0,3,1,0,3,1,1,2,2,3,1,0,3,0,1,1,0,2,3,1,0,3,1,2,3,2,3,0,1,1,2,0,2,3,0,0,3,1,3,1,0,0,0,2,1,0,1,0,1,2,1,0,1,2,0,1,2,1,2,0,0,1,2,0,1,2,1,1,2,1,2,0,0,2,0,1,0,0,1,2,2,0,0,0,1,1,0,1,1,0,0,0,1,0,1,1],[0,2,1,3,1,0,1,1,3,2,2,2,2,2,2,0,3,1,3,2,0,3,1,2,1,2,0,0,2,0,1,2,3,2,0,0,0,2,0,2,3,3,0,3,1,3,1,0,3,0,3,2,3,1,2,2,3,2,3,3,0,2,3,2,1,3,3,0,0,3,2,0,3,2,3,2,2,1,0,2,2,2,0,0,2,1,0,0,0,0,1,0,0,2,0,0,1,1,1,0,0,0,2,0,2,0,1,0,0,0,2,2,2,2,0,1,2,1,1,1,2,0,0,0,2,1,2,2,1,2,0,2,0],[0,0,3,2,1,2,2,3,0,2,3,3,1,3,0,1,1,0,3,2,2,1,3,3,2,0,3,1,1,3,2,2,1,1,2,3,3,0,1,2,2,1,1,1,3,3,1,1,1,2,0,2,3,1,1,3,0,0,3,0,2,3,2,0,0,3,1,2,3,3,1,3,3,3,2,0,0,2,1,1,2,0,0,1,0,2,0,2,0,0,1,1,0,1,0,1,1,1,0,1,0,0,1,2,0,1,0,2,1,2,2,2,0,0,1,0,0,1,2,0,0,1,0,0,1,2,2,0,0,1,1,2,2],[3,2,3,3,3,0,1,2,0,2,2,0,0,2,2,0,0,3,2,3,0,1,3,1,0,0,1,0,2,3,0,0,2,2,1,3,2,0,1,0,1,0,1,0,3,1,3,1,0,3,2,0,1,3,2,0,2,3,3,3,3,2,1,0,2,2,1,3,1,1,0,0,1,2,1,0,0,1,1,1,2,0,2,1,2,0,0,0,1,1,1,1,1,2,1,1,1,1,1,2,1,0,1,1,1,0,0,1,0,1,0,2,2,0,1,0,0,0,2,2,1,0,1,1,2,2,0,0,0,1,0,2,2],[1,1,3,2,0,1,2,1,0,1,2,0,1,3,2,1,2,3,1,2,1,1,0,3,1,1,1,0,0,1,2,3,2,3,1,2,0,3,0,1,0,3,1,2,1,2,0,3,0,0,3,2,2,1,2,1,1,0,1,1,2,1,2,0,0,1,2,0,1,3,3,3,3,0,2,2,2,2,0,1,2,1,0,0,2,1,0,2,0,0,0,1,1,2,2,1,0,0,0,0,1,0,0,2,0,0,1,1,0,2,1,0,1,2,0,0,0,1,1,2,0,0,1,0,1,1,2,0,2,0,1,0,1],[1,2,2,0,0,0,2,2,0,0,1,0,0,3,2,1,1,0,0,1,1,2,3,0,2,1,2,3,1,2,3,3,0,1,3,0,2,0,0,2,1,3,2,0,0,0,1,1,0,1,0,3,1,1,2,2,1,3,1,3,2,1,3,0,1,0,0,2,2,0,1,0,1,2,2,1,2,1,0,1,1,1,2,0,0,1,2,0,2,0,2,0,0,2,0,2,1,2,1,2,2,2,0,2,1,1,2,1,2,1,0,1,0,1,2,2,1,1,2,2,2,2,1,0,1,0,0,1,0,0,1,1,1],[1,2,0,1,2,0,1,3,3,3,0,3,0,0,1,2,1,2,1,2,0,0,1,2,2,1,0,1,3,2,2,3,1,0,3,0,3,3,0,1,2,2,3,1,1,0,2,1,0,2,3,2,1,3,2,1,1,2,3,0,0,1,0,3,2,2,1,0,1,2,0,0,0,1,1,2,2,2,1,0,2,2,2,1,1,2,1,0,2,1,1,1,2,2,1,1,0,0,0,2,2,2,0,2,0,1,2,1,2,1,2,1,0,0,0,1,1,2,0,2,0,1,2,0,0,2,1,1,0,2,1,0,1],[2,3,1,2,3,1,2,2,1,0,1,3,0,2,3,3,3,2,0,1,2,2,0,0,2,0,1,0,3,2,0,1,1,1,1,3,0,0,3,2,1,2,3,1,3,2,2,0,2,2,0,0,0,3,1,2,3,1,2,3,1,1,1,0,3,3,3,0,2,2,1,0,1,0,2,0,0,0,0,1,2,1,2,1,1,1,0,0,1,2,1,1,0,2,2,0,1,0,1,0,0,1,1,2,1,2,2,0,2,0,1,0,2,0,0,0,2,0,0,0,1,2,1,1,2,2,2,0,0,0,0,0,2],[0,1,3,1,1,3,3,3,1,0,3,0,0,0,2,0,0,3,2,0,3,2,3,2,1,2,2,0,2,3,1,2,3,0,1,2,0,1,3,1,1,2,3,3,2,1,0,1,3,1,1,1,3,3,0,0,0,0,0,3,3,1,1,0,2,1,0,0,2,1,2,0,0,2,1,1,1,2,0,1,0,2,2,0,1,0,1,2,1,1,0,1,0,1,1,1,2,2,1,2,1,2,2,2,1,2,1,0,2,1,1,0,1,0,1,1,0,1,1,0,1,2,1,1,1,0,0,1,1,1,0,0,1],[0,0,1,1,0,2,3,2,1,3,3,0,0,0,1,2,3,3,0,2,0,1,0,2,3,2,3,1,0,0,1,0,3,3,1,0,2,1,2,2,0,2,2,0,3,3,1,1,2,0,3,0,1,0,0,1,3,0,0,0,0,0,0,2,3,1,1,3,2,0,1,0,1,1,2,1,0,0,0,2,2,2,1,1,0,2,0,0,0,1,1,2,0,2,0,2,0,1,2,1,0,0,1,2,0,0,2,1,2,2,2,0,2,0,1,0,0,0,0,2,1,2,0,1,1,1,1,2,0,1,1,1,2],[1,0,0,1,1,2,2,2,2,3,1,0,1,3,3,0,3,3,3,0,3,3,1,1,3,0,0,0,0,1,0,0,0,2,1,2,1,1,0,2,3,3,2,1,0,3,1,0,0,3,1,0,0,0,3,3,2,3,2,2,1,1,1,3,2,0,1,1,1,1,1,2,1,0,1,2,2,2,0,1,2,0,0,1,1,2,2,2,0,1,1,0,1,2,2,1,0,2,2,2,0,2,0,2,0,1,0,2,2,0,2,2,1,1,0,2,2,0,2,2,2,1,0,0,0,2,2,0,0,2,0,1,1],[1,1,3,1,3,2,2,0,2,2,0,0,0,1,2,3,2,2,3,2,0,3,0,3,3,2,0,0,3,2,1,2,1,1,1,1,2,1,2,1,2,2,1,1,1,3,3,1,1,0,0,1,0,0,2,0,0,3,0,1,2,3,3,1,1,3,1,2,1,0,1,0,2,1,2,2,1,0,2,0,0,0,1,2,0,0,0,1,1,0,2,1,1,1,0,0,0,2,1,2,1,0,1,0,1,1,1,1,1,1,2,1,0,1,1,1,0,0,2,0,1,2,2,0,2,2,0,2,1,0,1,2,1],[3,0,1,3,0,2,1,0,3,1,3,2,3,3,1,1,1,3,3,0,2,1,2,1,1,0,2,1,0,2,2,0,3,2,2,2,1,1,1,3,2,0,3,3,2,0,0,0,0,2,3,1,0,1,1,1,2,3,2,2,0,2,1,1,2,0,0,0,0,0,0,1,2,0,2,2,0,2,0,1,0,0,1,0,1,1,2,1,0,0,0,2,2,0,0,1,1,1,0,0,1,1,2,2,1,1,0,1,1,1,0,2,0,0,2,1,1,0,2,1,1,1,0,1,1,0,0,2,1,2,0,2,0],[2,3,3,0,3,1,2,1,0,2,1,3,1,0,0,1,0,0,2,1,2,0,1,1,2,3,1,3,3,2,1,0,3,1,1,0,2,2,1,1,3,1,0,0,3,2,3,0,2,1,2,0,2,2,1,0,3,2,1,0,1,3,3,2,0,0,2,0,1,1,1,0,1,2,0,0,0,2,0,1,1,0,2,2,1,2,2,0,1,2,2,1,0,2,1,0,0,2,0,2,1,2,0,2,2,0,0,1,2,1,1,0,0,1,2,2,1,1,0,1,0,2,1,0,2,2,2,1,2,0,0,2,2],[0,3,3,2,2,1,2,3,2,1,1,1,0,3,2,2,0,1,0,3,0,1,0,1,2,3,3,2,3,3,0,0,3,1,0,2,3,3,3,3,2,2,1,2,1,3,2,2,1,1,2,1,3,3,0,2,0,3,0,1,0,1,3,0,0,2,1,2,1,1,2,0,2,0,2,0,0,1,0,1,0,0,2,2,2,1,1,0,1,2,1,2,2,2,2,2,1,0,1,1,2,1,0,2,2,0,2,2,1,1,0,2,0,0,1,1,0,1,0,0,0,2,2,2,1,1,0,2,1,1,0,1,1],[1,3,2,1,3,1,2,1,2,3,2,0,3,2,1,2,1,0,2,2,1,2,3,3,1,2,1,3,3,1,0,3,0,3,2,1,3,2,2,1,0,2,1,0,1,0,0,3,2,2,3,2,0,2,0,3,1,2,2,0,0,3,1,0,0,0,2,2,0,2,2,2,2,0,1,2,0,2,2,2,1,2,0,2,0,2,2,0,1,2,2,1,2,1,0,0,0,2,2,0,1,1,0,2,2,0,2,2,0,2,1,2,0,0,1,0,1,0,2,1,2,2,2,1,2,0,2,1,2,2,1,1,0],[3,2,0,0,3,2,2,0,2,0,3,1,2,3,3,0,3,1,0,0,1,3,1,1,2,1,2,3,3,0,2,2,0,0,0,2,3,3,1,3,0,1,2,3,0,1,0,2,0,1,2,0,1,2,0,3,2,3,0,0,3,1,0,1,0,2,1,2,0,2,1,0,0,1,0,0,2,2,0,0,2,2,2,0,2,1,1,2,2,1,0,0,1,0,1,1,0,0,0,1,0,1,2,1,2,1,0,0,0,0,2,2,0,1,0,2,1,0,2,1,0,2,2,0,0,2,1,2,2,0,1,2,0],[0,2,2,0,1,3,2,3,0,2,2,3,2,2,0,2,1,3,1,3,2,1,3,0,1,3,1,0,0,1,2,2,3,1,1,2,3,2,3,1,3,1,2,2,3,0,0,2,1,1,0,1,3,3,0,1,2,0,1,0,0,2,0,2,2,2,1,1,2,1,2,0,2,0,2,1,1,0,2,0,0,1,0,2,1,1,0,2,0,2,1,1,2,1,0,1,0,2,0,0,0,1,1,0,1,2,1,0,1,2,2,2,1,1,0,1,1,2,1,0,0,2,2,0,1,1,2,2,1,1,0,1,1],[3,0,0,3,1,3,1,2,3,1,0,3,3,0,1,2,0,2,0,3,2,3,2,2,3,1,0,3,2,1,2,3,0,0,2,0,3,0,3,3,0,3,2,3,0,0,3,2,2,1,0,3,0,3,2,1,1,1,1,1,2,0,0,1,0,2,2,0,0,2,1,1,2,0,2,1,1,0,1,1,0,0,2,0,1,1,2,1,2,0,2,2,2,2,1,0,0,2,1,0,0,1,0,2,0,1,0,2,1,1,1,1,1,0,0,2,0,0,0,1,0,1,1,1,1,1,0,0,1,0,1,2,2],[0,2,3,1,0,1,3,1,1,3,0,3,1,1,0,2,2,2,1,2,3,1,3,0,3,3,2,2,0,0,2,2,1,3,2,1,0,3,3,2,0,3,1,1,3,2,1,1,2,3,1,3,0,2,1,1,3,3,0,0,1,2,2,1,2,0,0,1,1,1,0,0,2,2,1,0,0,0,0,0,1,1,2,1,2,2,0,0,1,2,0,2,1,0,2,1,1,0,2,2,0,1,1,0,2,0,2,2,2,1,1,2,1,0,2,1,0,2,1,2,0,2,1,0,2,2,1,2,2,2,1,1,0],[1,2,3,0,2,2,2,2,0,3,2,0,3,0,0,0,0,0,1,0,3,0,0,3,3,3,2,1,0,1,0,3,3,2,1,3,0,3,1,2,1,2,3,3,2,2,2,3,0,2,3,2,0,3,1,2,1,2,1,1,1,1,1,2,1,2,1,0,0,2,1,1,2,1,0,1,1,2,2,2,1,0,1,0,0,0,0,1,0,2,1,2,0,2,0,1,0,1,1,1,1,2,1,1,2,0,0,1,2,0,0,0,1,0,2,0,2,1,2,2,2,1,2,0,2,1,0,1,0,2,2,2,2],[3,0,2,1,1,1,2,0,2,3,1,2,2,2,2,0,0,1,3,1,3,2,2,3,3,3,3,2,0,1,1,3,0,3,0,1,0,0,1,3,0,0,1,0,3,2,0,1,1,2,3,2,1,3,2,1,1,2,1,1,2,0,0,2,1,2,2,0,0,2,0,0,1,1,1,1,0,0,2,2,0,0,0,0,1,1,2,1,1,2,1,1,2,1,0,1,1,1,1,0,2,0,1,1,0,2,1,2,2,0,1,2,1,2,0,1,0,0,0,0,2,1,0,0,1,1,1,0,0,0,2,2,0],[2,0,3,3,3,3,1,3,1,3,2,2,1,0,0,2,1,0,0,0,0,2,3,2,3,2,3,0,0,0,2,0,1,3,3,3,3,0,0,2,1,3,1,0,3,3,1,2,0,0,3,1,1,0,0,2,2,2,0,1,1,2,1,1,1,0,0,2,2,0,0,2,2,1,1,1,0,1,1,0,1,2,1,0,2,2,1,0,0,0,0,2,1,1,1,0,0,1,1,2,0,1,2,0,2,0,2,2,2,2,2,0,0,1,2,0,1,0,2,1,0,1,2,2,2,1,1,2,1,1,2,1,0],[1,0,3,0,2,1,0,2,3,0,2,1,0,1,0,1,2,3,0,3,2,3,3,3,1,1,1,0,1,3,1,3,1,0,1,0,0,2,3,0,1,2,0,2,2,2,3,3,3,2,0,2,0,0,0,2,1,2,1,1,1,1,2,2,2,0,2,1,0,1,0,1,1,1,2,0,1,0,0,2,0,0,1,1,2,2,2,2,2,0,2,0,0,2,0,0,1,1,0,2,1,2,2,1,2,0,1,0,0,0,1,2,2,2,1,2,0,0,0,2,2,1,1,1,2,2,1,0,2,0,1,1,1],[2,2,3,2,2,0,1,2,2,0,0,1,2,2,3,2,0,2,3,0,1,0,3,3,2,2,2,0,3,0,3,2,2,1,3,0,1,3,0,3,2,3,3,2,0,2,2,2,1,3,2,3,0,2,1,0,2,1,1,1,1,0,1,1,1,1,2,2,2,0,1,1,0,0,1,1,2,0,1,0,2,0,1,0,1,0,2,2,2,2,2,1,2,0,1,0,2,0,2,2,0,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,0,1,0,0,2,0,0,0,1,0,0,2,0,1,2,1,1],[0,1,0,1,0,1,2,2,2,2,2,3,1,3,1,3,2,0,3,1,0,1,0,0,0,1,2,0,1,2,3,2,0,2,0,1,2,0,1,0,1,3,0,1,0,0,0,3,1,0,3,3,2,2,1,0,2,2,0,0,1,1,2,2,2,0,1,2,1,1,1,2,2,0,2,0,2,0,0,2,1,2,1,1,0,0,2,0,0,2,2,0,0,1,2,1,2,0,1,1,2,1,2,1,2,1,0,2,0,2,2,2,1,0,2,2,0,0,2,2,0,1,0,2,1,0,2,2,0,0,1,1,2],[2,0,0,1,1,1,0,2,0,2,3,0,0,0,0,1,3,3,3,2,1,2,3,3,3,3,2,2,3,0,1,1,2,1,0,1,2,0,1,1,1,2,3,0,1,1,0,0,0,2,1,1,2,2,1,1,1,1,2,2,1,1,1,1,1,0,1,1,1,0,1,2,0,0,1,2,2,2,2,2,1,2,0,1,1,1,1,1,2,2,0,0,0,2,0,1,1,2,1,2,2,0,0,2,1,1,0,0,2,2,2,1,1,1,2,0,0,0,2,1,2,0,0,0,2,2,2,2,1,1,0,1,2],[0,3,1,3,3,0,1,1,0,2,1,2,2,0,1,3,1,2,1,2,0,1,0,0,0,2,1,1,2,2,1,0,3,2,1,2,2,3,3,3,0,0,1,1,1,0,2,0,3,2,2,0,2,0,0,0,0,1,2,1,0,0,2,2,2,2,2,0,0,1,0,0,1,0,2,1,0,0,2,2,1,0,2,0,0,1,2,2,0,0,1,0,1,1,2,2,2,0,0,0,2,2,0,2,2,1,1,2,2,1,2,2,1,1,2,2,1,2,2,2,2,0,1,1,2,2,0,0,1,1,2,2,2],[3,1,0,1,3,0,2,3,0,3,1,3,3,3,1,0,0,3,0,1,1,0,0,3,1,3,0,2,3,2,2,2,3,3,2,3,0,2,1,3,0,1,3,0,1,1,3,0,3,2,0,0,2,1,2,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,1,1,1,0,2,0,1,1,1,0,2,1,0,0,1,1,1,2,0,0,2,2,1,1,1,1,2,1,0,1,2,2,0,0,2,2,1,0,1,2,0,1,1,0,1,0,0,2,0,0,0,0,1,2,0,2,0,2,1,0,1,0,2],[3,0,0,0,3,3,0,0,3,2,3,3,2,0,2,2,2,1,0,1,2,0,3,2,0,2,3,2,3,0,3,1,3,0,1,2,3,1,1,3,1,3,1,1,1,3,0,3,1,0,0,1,1,0,1,1,1,0,1,0,2,2,1,0,2,0,1,0,2,0,2,2,2,2,1,2,2,0,2,0,1,2,1,1,1,0,1,2,1,2,1,1,2,2,1,2,1,1,2,2,2,0,0,1,1,2,1,1,1,1,1,2,1,0,1,0,1,1,0,1,2,0,0,0,0,1,2,0,0,0,0,0,0],[2,0,0,0,2,3,1,3,1,0,0,2,2,3,1,2,2,3,1,2,1,1,1,3,2,2,0,1,1,1,0,1,2,0,1,3,1,0,3,3,3,3,1,2,2,1,3,2,1,2,0,2,1,0,2,2,1,1,0,2,0,2,0,2,0,0,2,1,2,2,0,1,1,1,1,0,2,1,1,2,0,2,1,1,2,1,2,0,0,1,0,2,1,2,2,2,1,2,0,2,0,2,2,2,2,1,1,2,1,2,2,1,2,2,2,1,1,0,0,2,0,2,2,0,1,1,2,0,0,0,1,1,2],[1,0,1,0,2,0,0,1,1,3,2,0,3,0,0,3,0,3,0,0,1,3,3,1,0,2,2,1,1,0,1,1,3,1,3,3,3,3,0,0,3,2,2,2,0,1,2,1,1,0,1,2,2,2,0,1,2,1,1,2,0,2,2,1,2,1,1,2,1,0,1,1,1,1,0,1,1,1,1,2,1,2,2,2,1,0,2,0,0,0,2,2,0,0,0,2,1,0,1,0,0,2,2,2,1,1,2,0,2,0,0,2,1,1,1,0,1,1,2,1,0,1,2,2,0,0,2,2,0,1,1,0,2],[1,3,1,0,3,1,0,2,3,1,3,1,0,1,3,2,3,1,2,2,3,2,2,3,3,0,0,1,1,2,0,1,3,2,3,2,3,3,0,2,0,0,2,3,2,2,2,1,1,1,0,1,2,2,2,1,2,1,0,0,2,2,1,2,1,1,2,0,2,1,0,2,0,1,1,0,1,0,0,1,2,0,1,2,2,0,2,1,2,2,2,2,0,1,0,0,0,2,2,2,0,2,1,1,1,2,2,1,2,1,0,1,1,0,1,0,2,1,0,1,1,2,1,0,0,0,0,2,0,1,1,2,1],[3,0,3,0,0,2,3,2,3,0,1,1,1,0,3,3,2,1,1,3,1,2,2,3,0,3,0,2,2,2,0,3,1,3,2,2,0,0,1,2,0,3,0,2,2,2,2,1,1,2,1,2,1,1,1,2,0,1,0,2,0,1,2,0,2,0,0,2,0,0,2,1,2,2,1,2,2,1,0,0,2,0,0,0,1,0,0,2,1,2,2,2,1,2,1,0,2,2,1,1,1,1,2,0,0,1,0,2,1,2,2,0,0,0,0,2,2,1,0,0,0,0,2,0,0,2,1,2,0,1,2,1,1],[0,0,3,1,1,2,3,1,3,3,3,1,2,0,2,3,0,1,1,0,1,0,2,2,2,1,2,2,2,3,2,3,2,1,2,2,2,2,2,1,1,2,1,0,1,2,1,0,0,2,1,1,0,2,1,0,2,1,0,2,1,2,2,2,1,1,0,2,2,1,2,1,2,2,1,0,1,2,0,0,0,2,2,0,2,0,0,2,0,1,1,0,2,0,0,2,0,2,1,0,0,1,0,2,2,2,0,1,2,1,1,1,1,1,2,2,1,1,0,0,0,0,0,1,0,0,0,2,0,0,2,2,1],[1,2,2,2,0,3,3,3,1,3,1,3,2,0,3,2,0,1,3,2,2,0,1,1,1,2,1,1,2,3,3,0,3,2,1,3,1,2,2,1,2,2,2,2,0,1,0,2,2,0,1,1,0,0,1,1,0,1,1,1,0,1,0,0,2,0,1,1,2,1,2,0,1,0,0,0,0,0,0,0,1,0,2,2,1,1,0,1,1,0,1,1,2,2,1,2,1,0,1,1,1,2,2,0,2,2,0,2,1,0,0,1,0,2,1,1,2,2,0,2,0,1,0,2,2,1,2,1,0,2,1,1,2],[1,3,3,2,3,1,3,2,0,0,2,0,2,3,3,1,2,2,3,3,1,0,1,3,1,0,2,1,1,2,2,3,1,0,1,1,1,0,2,1,2,0,1,0,1,2,2,1,0,0,2,2,0,2,1,2,1,1,0,1,1,2,0,2,2,1,2,0,1,1,1,2,0,0,1,1,1,0,2,2,2,1,1,0,1,1,1,2,1,2,1,0,0,1,2,1,1,0,1,1,2,0,1,1,2,1,0,1,0,2,0,2,2,2,2,2,2,2,0,2,1,1,2,2,1,1,2,1,1,2,2,2,1],[3,2,0,2,0,3,2,1,1,0,2,1,2,0,3,3,3,3,3,2,1,3,3,1,1,0,1,0,3,2,1,2,2,3,2,2,2,1,0,2,1,0,2,0,0,1,0,2,1,0,0,0,2,2,0,1,1,1,0,1,1,0,0,2,2,2,1,2,1,1,0,2,2,0,1,2,1,2,0,0,1,0,2,2,0,2,1,1,0,2,1,2,2,1,1,1,2,2,0,2,2,2,0,0,1,1,2,1,1,2,1,0,0,2,0,0,0,0,2,1,1,0,1,2,2,2,2,2,1,1,2,1,2],[3,3,3,0,1,2,3,1,0,2,3,3,1,0,2,0,0,2,3,0,1,3,1,2,0,1,1,1,2,2,3,1,0,1,0,3,0,0,2,2,0,2,2,2,1,1,0,2,0,0,0,1,1,1,1,2,1,1,2,0,1,0,2,1,1,1,1,2,1,1,0,1,2,0,1,0,0,2,1,2,0,1,0,2,2,2,1,0,2,1,0,2,0,2,2,1,1,0,1,2,1,0,0,1,0,0,2,1,2,2,1,0,1,0,2,0,0,2,0,1,0,1,1,2,1,2,0,1,0,2,2,2,0],[1,1,1,3,1,0,3,0,2,0,0,2,1,2,1,3,1,1,1,2,1,1,0,1,1,2,1,2,0,1,0,3,2,1,3,0,3,3,2,2,0,2,1,0,2,2,0,1,2,2,0,0,0,2,0,1,2,0,2,0,2,1,0,0,0,2,2,2,2,1,2,0,2,2,0,1,2,2,0,0,2,0,0,2,2,2,2,2,2,0,1,1,2,0,2,0,1,2,1,0,0,1,0,2,2,1,1,1,0,0,0,2,2,1,1,0,1,0,2,0,0,2,1,1,1,1,1,2,0,0,1,1,2],[0,1,3,1,2,0,0,2,2,1,1,3,1,0,3,2,0,0,3,3,1,3,2,3,3,2,0,1,1,2,1,3,0,1,2,3,1,0,0,2,2,1,0,0,1,2,0,2,2,0,1,2,0,0,1,0,2,2,1,1,2,2,0,1,0,2,0,1,2,0,1,1,0,2,0,1,0,0,1,0,1,1,1,2,2,2,0,0,2,0,1,1,2,2,0,0,0,2,1,0,2,1,1,1,1,0,0,2,0,1,1,0,0,1,2,0,0,2,0,0,2,2,1,1,1,2,1,0,0,0,0,2,1],[3,2,3,1,1,0,2,1,0,3,0,2,2,0,0,2,1,2,2,1,3,1,2,2,2,3,1,3,1,0,2,3,2,1,0,3,2,0,0,1,1,1,2,2,2,2,0,0,1,2,2,0,0,1,1,2,2,2,0,2,2,2,0,2,0,2,1,1,0,1,1,2,2,0,2,0,2,1,0,1,1,2,0,0,0,1,1,0,0,2,0,1,2,1,1,2,0,1,2,2,2,2,2,0,0,0,0,1,1,0,0,0,1,0,2,0,2,2,0,2,1,0,0,2,2,0,1,2,0,2,0,1,2],[1,0,0,1,2,3,1,3,1,3,0,3,0,3,0,3,3,3,3,3,3,2,3,0,1,3,0,2,2,3,1,2,2,3,0,0,0,2,1,0,1,1,1,0,2,2,2,2,1,1,2,1,0,1,1,1,1,0,2,2,0,1,2,1,2,0,2,1,1,0,2,1,2,1,2,0,2,1,0,1,0,2,1,1,1,1,0,0,2,2,1,2,0,2,1,2,2,1,2,1,2,0,2,0,0,1,2,0,0,2,0,0,0,1,0,2,0,1,0,1,0,2,2,0,1,1,0,2,2,0,0,2,1],[0,1,0,1,1,3,3,2,1,3,2,0,3,0,2,2,0,3,1,3,3,2,2,0,1,0,1,0,1,0,2,0,0,3,0,1,0,2,1,1,0,1,0,2,2,0,1,0,2,0,2,1,2,0,1,1,0,1,1,0,1,0,0,0,2,1,1,1,2,2,2,2,1,1,1,2,2,0,0,1,1,2,1,2,0,1,0,0,0,2,0,0,1,1,0,0,2,0,1,2,1,1,1,0,0,2,0,0,2,1,1,0,0,0,0,1,1,0,0,0,0,1,2,2,0,2,2,2,0,2,1,1,0],[0,1,3,0,2,2,2,0,3,3,3,2,2,0,1,2,3,1,0,0,0,3,2,0,0,0,1,0,2,2,0,0,3,1,2,0,0,0,0,1,1,0,2,0,0,2,2,0,2,1,0,2,0,0,2,0,0,2,2,0,0,0,2,0,1,2,1,0,1,1,1,1,1,1,0,0,0,2,1,0,1,0,1,2,0,0,2,1,0,1,1,0,0,0,0,0,2,2,2,2,1,2,0,1,2,0,2,0,2,2,2,2,2,2,1,0,0,0,2,0,1,1,2,2,2,2,0,0,0,1,0,2,1],[1,1,0,3,0,3,1,1,0,2,2,3,2,0,1,3,0,3,2,3,1,1,1,1,0,3,1,3,2,0,2,2,1,1,0,2,0,1,2,1,2,2,0,2,1,2,1,0,0,1,0,1,0,2,1,0,1,0,1,2,1,2,0,2,1,0,2,2,0,2,2,1,0,1,2,0,2,2,1,1,2,1,0,0,1,0,0,2,0,0,0,2,0,1,1,1,0,0,0,0,0,0,0,2,0,2,2,0,2,1,2,2,2,0,2,2,1,2,2,0,1,1,0,2,0,1,1,1,0,0,1,2,1],[0,1,0,3,3,1,1,1,0,0,2,2,0,1,0,2,2,2,2,1,2,0,3,0,1,3,3,0,0,3,1,0,2,0,0,1,2,2,0,1,2,1,2,2,2,0,1,1,2,1,0,2,1,0,0,2,1,0,1,1,0,2,1,2,0,0,1,2,1,2,0,1,1,1,1,1,2,0,1,0,0,1,1,1,0,1,0,1,1,1,0,2,0,0,2,1,0,2,2,2,1,1,0,0,0,1,2,1,0,0,1,0,1,1,0,1,2,2,0,2,2,2,1,1,0,0,0,0,1,0,0,1,1],[1,0,2,3,0,0,1,2,1,2,3,1,2,2,2,0,2,0,0,2,0,1,0,3,2,1,3,2,0,3,2,1,2,0,1,0,0,2,2,0,2,1,2,0,1,2,0,2,2,1,1,2,2,0,0,2,0,1,1,0,1,1,0,0,2,2,2,2,1,1,1,2,2,0,2,1,0,0,1,1,1,2,1,0,2,0,1,2,0,2,0,0,0,2,0,1,2,0,2,1,0,1,0,0,1,2,1,0,2,0,2,1,2,2,1,2,0,2,1,2,2,0,0,2,2,0,1,2,0,1,2,0,2],[1,1,1,0,0,0,3,1,0,2,0,0,3,0,2,2,2,1,1,0,0,0,3,2,1,1,0,1,2,1,0,1,1,0,0,2,1,1,2,0,0,0,1,1,1,0,1,2,1,0,1,0,0,1,1,1,2,0,0,2,1,0,1,2,1,1,0,2,1,1,2,1,1,1,0,2,2,2,1,2,2,1,0,1,0,2,2,0,2,1,1,1,0,0,1,0,1,2,1,2,2,0,0,1,0,0,2,1,2,1,1,2,1,2,0,0,0,2,0,1,0,1,1,2,2,1,0,0,1,1,1,1,2],[1,3,3,1,1,0,2,0,2,1,3,3,1,1,3,2,2,1,2,1,1,0,3,1,1,2,1,1,1,0,1,2,1,0,2,0,0,1,0,0,1,1,0,0,0,1,2,2,0,2,1,2,0,2,1,0,0,2,1,0,0,2,2,2,1,0,2,0,1,2,1,0,0,2,0,2,2,0,0,2,0,2,0,0,1,1,2,0,2,1,0,1,1,0,1,0,2,1,2,0,2,0,2,0,1,2,1,2,0,0,2,1,0,1,1,0,1,1,2,2,2,0,2,2,2,0,0,1,2,0,2,1,2],[3,1,1,2,2,2,1,1,3,2,2,3,1,1,2,0,1,0,1,1,1,2,3,1,1,1,0,2,2,2,1,0,1,2,2,1,2,0,2,0,1,0,0,1,2,0,0,0,2,2,2,2,2,2,0,1,2,1,0,2,1,1,2,1,2,2,0,0,1,1,0,1,1,2,1,0,2,1,2,2,1,0,2,2,0,1,0,2,2,2,1,1,0,1,0,0,0,2,2,2,2,0,0,0,2,1,1,1,0,0,0,1,1,1,2,2,1,1,0,1,0,0,1,0,2,2,0,0,1,0,0,0,0],[2,1,0,2,0,1,0,0,3,0,2,0,1,3,3,0,1,3,0,0,3,3,2,3,1,3,0,0,0,1,1,1,0,1,1,1,0,1,2,0,0,1,2,1,0,0,0,0,0,0,1,2,0,2,2,2,0,1,1,0,1,2,2,2,0,2,0,1,0,2,2,0,2,2,1,1,2,1,1,2,0,2,1,0,0,0,2,0,0,1,2,2,2,2,2,2,0,0,0,2,0,1,1,2,0,2,0,1,0,1,2,1,1,2,2,2,1,0,2,1,2,0,1,2,2,0,2,2,0,1,0,0,1],[1,2,2,2,2,1,2,2,1,2,0,2,0,3,0,2,2,3,0,1,0,3,0,1,2,0,2,2,1,2,0,0,1,1,0,0,0,2,0,2,1,1,0,0,2,2,0,2,0,2,2,1,2,1,2,1,1,2,2,1,1,1,2,0,0,1,1,0,0,0,1,1,2,1,2,2,0,1,2,0,0,0,0,2,0,1,1,0,1,1,0,1,1,0,2,1,1,1,1,0,0,0,0,2,0,1,0,2,2,0,0,1,2,0,0,2,0,0,0,1,2,0,2,0,1,2,2,2,2,1,0,0,0],[1,0,0,0,2,3,2,1,0,3,0,0,2,0,3,0,0,2,1,0,2,1,0,2,1,0,0,2,2,1,1,0,0,2,1,2,1,2,2,1,1,2,0,1,0,2,2,2,1,0,0,2,0,2,0,2,2,1,2,2,1,0,0,1,1,2,2,2,0,0,0,2,1,2,0,0,0,0,0,2,0,0,1,2,2,1,0,2,1,1,0,2,1,1,2,1,2,0,1,1,2,2,2,0,0,2,2,2,0,1,2,2,1,2,1,1,1,2,0,2,0,1,2,1,2,1,2,0,0,1,1,0,0],[3,3,0,0,1,0,1,0,0,0,0,1,2,0,2,0,0,0,3,2,1,1,2,2,0,2,2,0,1,1,1,1,0,0,0,1,0,0,2,2,1,1,0,2,0,0,2,1,1,0,1,0,0,0,2,0,0,0,0,2,2,0,1,1,2,2,1,0,1,0,0,2,2,2,1,1,0,2,1,1,1,0,0,1,2,1,1,0,0,2,1,1,1,0,2,1,1,0,2,1,1,0,1,1,1,1,2,0,1,0,1,2,1,0,0,2,2,1,0,0,1,1,0,1,0,2,1,2,0,0,0,2,2],[3,3,0,1,1,3,3,3,1,3,3,2,2,1,0,1,2,1,3,3,1,2,1,1,2,1,2,1,1,0,1,0,1,0,1,0,1,2,1,0,0,1,1,1,1,0,1,0,0,2,1,2,2,2,1,2,2,0,0,2,0,1,2,1,1,0,0,0,1,2,2,1,0,1,0,0,0,1,1,2,0,2,2,1,2,2,1,2,0,2,2,0,1,2,0,2,2,2,0,0,2,1,2,1,1,0,2,1,1,2,1,2,0,2,2,0,2,2,0,0,1,0,0,1,2,2,1,1,2,2,2,2,2],[2,1,0,2,3,1,2,2,3,3,3,2,3,0,3,2,1,1,1,3,3,1,2,1,2,1,2,1,0,2,2,0,2,1,2,0,0,0,1,2,0,0,1,1,1,0,1,2,0,1,1,0,0,1,2,1,1,1,1,1,0,2,2,1,2,0,1,1,1,0,0,1,1,1,2,0,1,1,2,1,1,2,0,0,1,0,2,1,0,1,1,0,2,1,0,0,2,2,1,0,0,0,2,0,2,0,0,0,2,0,0,1,2,0,2,0,0,0,0,1,2,2,2,1,2,2,1,0,1,1,0,2,2],[1,0,0,2,3,0,0,2,1,2,3,2,1,3,3,1,2,1,1,1,0,2,0,0,0,0,1,1,1,2,2,2,1,2,2,0,2,2,2,0,1,1,1,1,0,0,1,1,2,2,2,0,0,1,0,0,1,1,0,2,2,0,2,2,2,1,2,2,0,0,0,2,1,1,0,0,0,1,0,1,2,0,2,1,2,2,1,1,0,0,0,0,2,0,0,0,1,2,1,0,1,0,1,1,1,1,2,0,2,0,1,0,2,0,2,2,2,2,0,2,2,0,1,1,0,0,2,0,0,1,1,0,2],[1,3,3,3,2,1,3,1,2,2,1,1,1,0,0,2,3,0,1,2,0,2,0,2,1,2,0,1,1,1,0,0,0,2,2,0,1,1,0,0,2,1,0,2,2,0,1,0,2,2,2,1,0,2,0,1,1,1,2,1,1,2,1,1,0,2,1,1,0,1,1,2,2,2,0,0,1,1,1,0,1,0,1,2,0,2,1,1,0,1,1,0,1,2,1,1,2,2,2,2,0,0,1,1,2,2,2,1,2,2,0,2,2,2,0,2,0,2,2,2,2,2,1,2,2,2,2,1,2,1,0,0,1],[0,3,0,2,3,3,2,1,0,3,2,3,3,0,3,2,0,0,0,0,2,1,2,2,0,0,0,1,0,0,0,2,0,2,2,1,2,0,2,0,2,1,1,2,2,1,2,2,2,2,0,2,1,2,0,2,2,0,0,2,0,2,1,0,0,1,1,0,0,1,1,1,1,1,1,0,0,1,1,2,1,1,0,0,0,2,1,1,0,0,1,1,2,2,0,1,2,1,2,2,2,1,0,1,2,1,2,2,0,1,1,2,2,0,2,1,2,0,0,0,2,0,1,1,1,1,2,0,0,0,1,0,1],[2,1,2,2,2,0,3,3,0,3,2,1,2,2,2,2,0,1,2,0,0,1,2,2,1,2,0,0,2,1,2,2,1,2,2,0,1,1,2,1,1,0,0,0,2,0,2,2,0,1,1,0,0,2,2,0,2,1,1,1,0,2,0,2,1,2,1,1,1,1,1,0,0,2,1,0,2,0,0,1,2,1,0,2,2,0,2,2,2,1,1,1,0,1,1,2,0,0,0,2,0,2,0,2,0,1,0,2,1,0,1,2,2,1,1,0,1,2,0,1,0,2,1,1,2,0,0,2,0,2,1,0,0],[0,3,3,0,0,1,0,2,1,3,2,0,1,0,3,3,2,2,0,1,2,0,2,0,1,0,2,2,1,1,1,1,2,2,2,1,1,1,2,0,0,0,0,0,1,0,0,1,2,0,2,1,0,1,2,2,2,2,1,2,1,2,2,1,0,1,0,0,0,0,2,2,1,1,2,2,1,0,0,0,1,1,2,2,0,1,1,2,2,2,2,1,0,1,0,1,1,0,2,1,0,0,2,2,1,0,0,1,2,0,2,1,2,2,1,0,2,1,1,0,2,2,1,0,2,2,1,0,0,0,0,0,0],[2,3,0,2,0,0,2,0,0,3,1,1,2,0,1,1,1,1,1,1,0,1,2,0,2,0,0,0,2,2,0,2,1,1,1,0,1,0,1,0,2,1,2,1,0,2,2,2,1,2,2,1,2,2,2,2,1,0,0,0,0,0,2,0,0,2,0,2,1,1,2,0,2,2,2,1,0,0,1,0,2,1,0,1,0,0,2,2,0,1,1,1,0,1,1,0,2,1,2,1,0,0,2,1,2,1,2,2,0,1,1,0,1,1,2,1,1,1,1,2,2,1,2,1,0,1,2,0,2,0,2,0,0],[2,1,3,3,3,0,0,3,3,1,3,1,2,2,0,1,1,1,1,2,2,2,2,1,1,2,1,2,1,1,1,0,2,2,1,1,2,0,2,0,0,0,0,0,1,1,0,1,2,2,1,0,0,2,2,0,2,0,2,2,0,0,1,1,0,2,0,0,0,0,0,2,2,0,2,0,0,2,1,2,2,0,0,1,0,2,0,1,0,1,1,0,0,0,1,0,1,1,1,1,0,0,1,2,2,0,1,1,1,1,2,2,1,1,0,2,2,1,1,1,0,1,2,0,1,1,0,2,0,0,0,2,0],[3,2,2,1,3,1,1,2,3,0,0,2,1,2,0,2,1,2,2,0,1,1,2,2,0,1,2,0,1,0,2,1,2,1,0,0,1,1,1,2,2,1,2,0,0,2,1,1,0,0,0,2,2,0,1,2,2,1,1,0,2,0,1,2,2,1,1,2,2,0,0,2,1,0,2,1,2,0,0,0,1,1,1,2,2,2,1,1,1,2,2,1,2,0,2,0,0,1,2,2,2,0,0,0,2,0,1,1,0,0,1,0,2,0,1,0,1,2,0,0,2,0,2,0,0,1,2,1,1,0,2,1,2],[3,1,2,2,3,2,0,3,2,3,1,2,1,1,0,2,1,1,0,2,1,2,0,2,2,0,2,2,2,2,0,0,1,2,1,1,1,1,0,2,0,1,1,0,2,1,1,1,1,1,1,1,0,1,1,1,0,0,2,2,0,2,1,2,0,1,2,2,2,0,0,0,1,0,0,2,0,1,0,0,1,2,1,2,2,1,2,2,1,2,2,1,2,2,0,2,1,0,2,2,0,2,1,0,1,0,0,0,1,0,0,1,1,0,2,0,0,1,2,2,2,2,0,2,2,0,1,1,1,1,1,1,0],[0,0,2,1,1,2,0,1,1,1,0,2,2,0,0,2,1,2,0,1,2,1,1,2,2,2,0,2,2,0,1,2,1,2,0,1,1,0,2,0,0,2,1,1,0,0,1,2,1,2,0,2,0,1,0,0,0,1,1,0,2,2,0,0,2,2,0,2,0,1,1,2,2,1,1,0,1,1,2,1,1,1,0,1,1,0,1,2,0,0,1,1,0,0,1,2,1,1,2,0,0,0,2,2,1,1,0,1,0,0,1,1,1,0,2,2,1,2,1,2,1,0,2,2,0,1,0,0,1,2,0,0,1],[0,2,0,1,2,1,1,0,1,0,2,1,2,0,1,1,0,1,2,1,1,1,1,0,2,1,0,1,0,2,1,1,0,2,0,0,2,1,2,1,2,2,2,2,2,1,1,2,2,2,2,1,1,2,0,1,0,0,1,2,2,2,2,1,2,0,0,2,1,0,2,1,2,0,1,0,2,1,0,0,1,2,1,0,1,1,2,0,2,2,0,0,2,0,0,0,1,2,0,2,1,0,1,1,2,1,1,1,2,2,2,0,0,0,0,0,0,1,0,0,2,2,1,0,0,2,0,1,0,0,2,1,0],[3,3,1,1,2,3,2,3,3,0,2,2,1,1,0,1,0,0,0,1,1,0,0,0,1,0,2,0,2,0,0,1,1,0,1,2,1,0,2,0,1,0,2,1,1,2,0,0,0,1,1,1,2,2,2,2,0,0,1,0,0,2,2,1,2,1,2,0,0,0,2,1,1,1,1,0,0,0,1,1,1,0,2,2,0,1,2,0,0,0,2,1,0,0,1,0,0,1,1,1,2,2,2,1,1,1,0,2,0,2,1,2,1,2,1,1,1,2,0,1,1,2,1,0,2,1,0,2,2,1,2,1,2],[3,2,1,1,1,2,3,2,2,0,1,1,1,2,0,2,1,1,0,0,1,2,2,1,0,1,1,1,2,2,2,2,0,0,0,1,2,0,0,0,0,1,2,2,2,1,1,0,1,1,1,0,0,0,1,2,2,1,2,1,1,2,2,2,2,0,2,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,2,2,0,0,1,0,0,0,1,2,1,1,0,2,1,1,0,2,0,0,0,1,1,0,0,2,0,2,0,0,2,1,1,2,2,1,1,0,0,2,2,0,1,2,0,0,1,2],[1,0,0,0,2,0,1,2,2,1,2,0,2,1,0,2,2,0,1,1,1,0,1,1,0,2,2,1,0,0,1,0,2,1,2,2,0,0,2,2,2,0,0,2,1,2,0,2,0,0,0,1,1,1,0,2,2,0,0,1,0,1,1,1,1,1,0,2,1,1,0,2,2,2,2,2,2,1,0,2,1,2,0,0,1,2,2,1,1,1,0,0,0,1,2,2,0,1,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,1,2,0,1,1,2,0,2,0,0,2,0,2,1,0,2,1,2,2,2],[1,1,3,0,1,0,2,2,2,0,1,0,2,0,0,1,2,2,0,1,1,2,1,2,0,0,1,2,0,2,0,1,2,0,0,1,0,0,2,2,1,1,2,2,0,1,2,1,2,1,0,2,2,0,2,1,0,2,2,0,1,0,0,0,1,0,0,0,2,2,2,0,2,2,2,0,0,2,1,0,1,1,0,0,2,1,2,0,1,2,0,0,0,1,0,1,1,1,2,0,0,2,1,0,1,2,1,0,1,0,0,1,0,1,1,2,0,1,0,2,2,1,2,0,0,1,2,1,2,0,1,1,1],[1,0,3,1,0,2,0,1,1,1,0,0,1,1,2,0,0,1,0,2,0,1,0,1,2,0,0,1,1,0,0,2,2,2,1,0,2,2,1,2,0,2,2,2,1,1,2,1,2,2,0,1,1,1,2,1,1,1,0,0,0,0,2,1,1,1,0,1,0,1,1,1,2,1,2,1,1,2,1,2,0,2,1,0,2,2,1,1,0,2,1,2,1,2,1,0,2,1,1,1,0,0,2,0,0,1,0,1,0,1,0,2,2,0,2,1,0,2,0,0,2,0,1,0,0,2,2,1,0,2,1,0,0],[2,0,2,2,1,0,2,1,2,0,1,1,0,1,2,1,2,0,2,1,2,2,2,2,0,1,0,2,2,0,2,1,1,0,1,2,0,2,1,0,2,2,2,0,1,1,0,2,0,0,1,1,0,0,1,1,0,1,1,0,2,0,2,1,2,0,0,0,2,1,0,1,1,0,2,2,2,0,2,1,1,2,1,1,0,0,2,0,2,0,1,0,0,2,0,1,2,2,1,1,0,2,0,0,1,2,1,2,0,0,1,1,0,2,0,0,1,1,2,2,2,1,1,1,2,1,2,0,2,2,2,0,2],[3,0,2,0,2,2,0,1,2,0,2,1,0,2,2,1,1,1,1,1,0,2,0,2,1,2,2,2,0,0,1,2,1,0,1,2,0,0,0,2,2,2,1,0,1,1,0,2,2,0,2,2,2,2,2,2,1,0,2,1,2,1,1,2,0,2,1,2,2,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,2,0,1,0,0,0,2,2,2,2,2,0,1,2,1,0,0,2,0,0,2,1,1,2,0,0,1,2,0,2,0,1,1,0,2,1,1,1,2,1,1,0,1,2,2,0,1,0,2],[0,1,2,2,1,0,2,0,1,0,1,1,0,1,1,0,0,1,0,0,0,0,0,1,1,2,2,0,2,0,1,1,0,0,1,0,2,0,0,2,2,2,2,0,1,1,2,0,2,2,2,0,2,0,0,2,2,1,1,0,1,1,1,2,2,2,2,1,1,2,1,2,0,1,1,2,2,0,2,0,0,0,2,2,2,0,0,0,0,2,1,2,1,1,2,1,0,2,0,2,1,2,2,2,2,1,1,1,1,1,0,1,1,2,0,1,2,0,2,1,1,2,0,0,0,2,2,0,1,0,0,2,2],[3,0,1,2,2,1,2,1,1,1,0,1,0,1,0,2,1,1,0,2,0,2,1,2,2,0,0,2,2,2,0,0,0,0,2,1,0,1,1,2,2,1,1,1,0,2,1,2,0,0,0,1,2,1,0,0,1,2,0,2,2,0,0,0,0,2,0,1,2,2,2,0,2,2,2,1,0,0,1,1,0,1,0,2,1,1,1,1,0,0,0,2,2,1,0,0,2,0,1,1,0,2,2,1,1,0,2,0,1,0,2,2,0,0,2,1,1,0,1,0,2,2,0,2,0,0,1,0,2,0,0,1,2],[2,2,0,2,1,2,1,2,2,1,1,2,0,0,0,0,1,0,1,0,2,1,2,1,0,1,0,0,0,1,0,0,0,0,2,2,0,1,0,1,2,1,2,0,2,0,1,1,1,1,2,0,0,0,0,0,2,0,1,1,1,2,1,2,1,0,2,1,1,1,2,1,0,2,2,1,1,1,1,1,0,1,1,1,1,1,0,2,1,1,1,0,2,1,2,2,0,0,0,1,1,0,1,2,1,0,0,1,1,2,0,1,1,1,1,0,2,2,2,1,1,1,1,2,1,0,0,0,2,0,1,0,1],[0,1,1,0,2,2,2,2,2,2,1,2,2,1,0,1,0,0,0,2,1,1,1,1,1,2,1,1,1,0,2,0,2,2,1,1,1,0,2,1,0,0,0,2,0,0,1,0,2,0,2,2,0,0,1,1,2,0,1,1,2,1,2,0,1,0,2,0,0,1,2,1,0,2,1,1,1,2,2,1,0,1,1,1,1,2,0,0,0,2,1,1,0,2,1,1,2,0,1,1,2,2,0,0,2,0,0,0,1,1,0,1,0,2,1,1,1,1,0,1,2,1,2,2,2,1,2,0,0,2,1,2,2],[2,2,1,0,1,0,0,1,0,1,1,0,0,2,0,2,1,1,2,1,1,0,2,1,2,1,0,1,1,0,2,1,1,0,0,1,2,2,0,1,1,1,1,1,1,2,0,1,1,2,2,0,1,0,2,1,2,2,2,2,2,2,1,1,1,0,2,0,1,1,1,1,0,0,0,2,1,1,1,2,2,0,1,2,0,0,2,1,2,2,2,1,1,2,2,1,1,1,0,0,0,2,0,0,1,0,0,0,0,1,1,1,1,2,1,1,1,2,2,2,2,2,1,0,0,0,0,2,0,2,2,0,1],[1,2,1,1,1,2,1,1,2,2,0,2,1,0,2,0,2,0,0,1,0,2,2,1,1,0,1,2,2,1,1,1,0,0,1,0,1,1,0,1,1,2,2,2,2,0,1,1,0,1,1,0,0,1,1,1,1,1,0,2,1,1,1,1,1,1,2,2,1,2,1,1,1,0,1,2,1,1,1,2,2,2,1,0,2,1,0,2,1,2,1,2,0,1,1,0,1,1,0,0,0,1,2,1,2,2,2,2,0,1,1,0,0,2,0,0,1,1,1,2,1,0,0,0,0,2,2,0,0,0,2,0,0],[2,0,2,0,2,1,0,1,2,1,0,1,1,1,0,1,1,1,2,2,1,0,2,2,2,0,2,1,1,1,0,0,1,1,2,1,2,2,1,2,0,2,0,1,0,1,0,0,1,0,1,0,2,1,0,2,2,1,0,0,2,1,2,2,0,1,1,0,1,2,1,1,1,1,1,0,2,0,2,2,2,0,1,0,0,0,2,0,0,2,0,0,2,2,0,0,0,2,1,0,0,0,0,2,1,2,1,0,2,2,0,1,1,1,1,0,2,0,1,2,1,0,2,1,0,2,0,2,2,1,1,2,1],[1,1,0,2,0,0,1,0,2,0,0,1,2,1,2,1,2,0,2,0,2,1,2,0,0,2,1,2,1,0,1,2,2,0,2,2,1,2,2,0,0,1,1,0,0,0,1,0,0,2,2,0,0,0,1,1,1,2,0,0,0,0,1,2,0,1,1,0,0,1,0,2,0,0,0,2,1,2,0,1,1,2,1,0,0,0,1,1,0,0,0,0,0,2,0,1,2,1,0,1,2,0,0,1,0,2,1,2,0,1,1,0,0,0,2,0,1,0,1,1,1,1,1,1,0,2,2,2,1,0,0,1,2],[1,2,0,1,0,0,0,0,1,0,1,0,0,1,2,1,2,0,2,2,2,2,1,0,1,1,1,1,1,2,1,0,1,0,0,1,0,1,0,0,0,2,0,0,0,2,2,2,1,0,0,0,1,2,0,0,1,1,2,2,2,0,0,2,1,2,0,2,2,1,0,1,0,0,2,2,2,0,1,2,1,1,1,0,2,2,1,1,0,2,2,1,1,2,0,0,1,2,2,2,2,2,0,1,0,2,1,0,2,2,0,1,0,0,0,0,1,2,2,2,0,2,1,0,2,2,2,1,2,0,2,2,0],[2,1,1,1,1,2,0,1,1,1,0,1,1,1,1,2,0,1,2,2,1,1,1,0,1,0,2,2,2,2,0,1,2,2,1,2,0,1,0,0,1,1,0,1,0,1,2,1,1,2,0,1,1,0,2,1,0,0,2,0,0,0,1,2,0,0,0,1,1,1,2,1,0,0,1,0,1,2,1,0,0,1,1,0,0,0,0,0,1,1,2,2,2,1,2,2,1,2,2,1,2,0,2,0,2,2,1,0,2,2,2,1,0,2,0,0,0,1,0,0,2,1,0,1,0,0,1,1,2,0,2,1,0],[1,0,0,2,2,1,1,0,1,0,0,2,2,1,0,0,1,2,1,2,1,2,2,1,1,0,1,2,0,2,1,0,0,1,2,1,1,2,1,0,0,1,0,1,0,0,0,0,1,1,1,1,2,1,0,1,2,1,0,2,1,0,2,2,2,2,1,2,0,0,2,0,1,0,0,0,2,0,0,1,0,0,2,1,2,2,2,2,0,0,2,2,2,1,0,1,0,0,1,0,1,1,0,1,2,0,1,0,0,2,1,1,1,0,1,2,0,1,1,2,1,2,0,0,2,1,0,1,2,1,0,1,0],[1,1,1,1,1,1,1,1,0,1,2,0,1,1,0,1,0,2,0,1,0,2,0,2,2,2,0,2,2,0,0,2,0,0,1,0,0,2,0,0,2,0,1,1,1,1,1,1,2,2,2,2,1,0,1,2,0,0,2,0,2,1,2,1,0,0,2,0,2,1,2,0,0,1,2,1,1,0,0,2,1,0,0,1,0,2,2,1,2,0,0,0,1,2,2,0,2,1,0,0,0,2,0,2,1,0,2,2,2,0,1,1,2,1,1,0,2,1,0,2,1,0,0,1,1,0,0,1,0,0,1,2,2],[2,2,2,0,2,2,1,1,0,0,1,0,1,0,1,2,2,0,2,2,2,1,0,2,2,1,1,2,2,1,2,0,2,2,0,1,0,1,0,1,0,0,2,2,2,0,0,2,0,1,1,1,2,1,2,1,0,1,1,1,2,2,1,2,1,1,1,0,2,2,2,2,0,1,2,1,1,0,2,0,2,1,2,0,1,0,2,1,0,1,0,1,2,0,1,0,2,0,1,2,2,0,2,1,2,0,1,2,1,1,0,1,0,1,2,2,2,1,2,2,1,1,1,2,0,2,1,2,1,1,0,1,2],[0,2,2,1,0,0,0,1,2,2,2,0,0,0,0,0,1,1,1,1,1,0,2,2,0,1,0,1,1,1,1,0,1,2,1,2,1,1,2,2,2,2,1,1,2,1,1,0,0,0,2,2,1,0,1,1,0,0,1,1,0,1,0,0,2,2,2,1,1,2,1,1,2,1,0,2,1,2,2,1,2,0,2,0,2,0,1,2,2,2,1,1,1,1,2,1,1,2,2,1,1,1,0,2,0,0,0,2,0,2,0,2,1,1,0,1,2,0,2,1,2,1,1,1,0,2,1,2,0,1,0,0,1],[2,2,2,1,0,0,0,0,2,2,0,0,2,1,2,0,0,1,0,0,1,1,1,1,1,0,0,2,1,1,1,1,1,1,0,2,0,2,0,1,2,0,2,1,1,1,0,0,0,2,1,2,2,2,1,0,0,0,0,2,1,1,2,0,2,1,0,2,0,2,2,1,0,2,0,0,0,0,2,2,2,1,2,1,1,0,2,1,1,2,1,0,1,0,2,2,2,0,0,2,1,1,0,1,1,0,2,2,0,2,0,0,0,2,1,0,2,0,2,2,2,2,1,2,1,0,1,2,1,0,2,1,0],[1,1,0,0,1,2,1,1,0,2,0,1,0,2,2,0,1,1,1,0,2,2,0,1,2,1,2,1,0,2,2,1,2,2,1,2,2,2,1,0,1,0,2,1,0,0,1,1,2,0,0,0,0,2,0,2,1,0,0,1,1,0,2,0,2,1,2,0,0,2,1,2,1,2,2,2,0,1,1,0,0,0,0,1,0,0,0,2,0,1,0,2,2,0,0,2,2,2,0,2,0,0,0,1,1,2,0,2,2,0,1,1,1,0,1,1,0,0,2,2,1,1,0,2,2,0,0,1,1,2,1,0,2],[0,2,0,1,0,0,2,0,1,1,0,1,2,0,2,0,1,2,2,1,0,2,0,2,2,2,2,0,0,1,2,1,0,0,0,1,1,1,2,2,0,1,0,2,2,1,1,1,2,2,2,0,1,1,0,2,0,2,2,0,2,0,0,2,1,0,0,0,1,0,2,1,1,2,2,0,1,1,1,2,1,2,0,1,0,0,2,0,0,0,0,0,2,0,0,0,2,2,1,2,1,1,0,2,1,2,2,0,1,2,1,1,0,1,0,0,1,2,0,1,0,1,1,2,1,2,0,0,1,2,0,2,2],[0,2,2,1,0,0,0,1,1,2,2,1,2,2,0,0,0,0,0,0,0,0,1,1,2,0,1,1,0,0,0,0,2,2,0,0,0,1,1,1,0,2,0,1,1,0,0,1,2,1,2,1,0,0,1,1,0,1,0,2,2,0,1,1,1,2,0,2,1,2,1,0,0,2,1,1,0,2,2,0,1,1,2,2,0,1,2,0,2,1,1,1,1,0,2,2,2,0,0,2,1,2,0,2,0,1,1,0,2,2,0,0,0,1,2,2,0,0,1,0,2,1,0,2,1,2,1,0,2,2,1,0,1],[2,2,2,0,1,2,2,2,0,2,1,2,2,2,1,0,2,0,0,2,0,1,2,1,1,1,0,0,0,1,0,2,2,2,0,1,1,0,2,2,1,0,1,2,1,2,1,2,0,1,1,0,0,1,2,1,2,2,2,0,0,2,2,1,0,1,0,1,2,1,2,1,2,0,1,2,0,0,1,1,2,1,1,0,1,0,0,0,2,2,2,0,0,2,1,0,2,2,2,2,2,0,2,2,2,1,0,0,2,2,0,1,2,2,2,0,0,0,2,2,1,0,1,2,2,2,1,1,2,2,2,2,1],[1,0,0,2,1,2,0,1,2,0,1,2,1,2,0,2,1,2,2,2,2,1,1,1,1,0,1,2,0,2,2,2,1,2,0,0,1,0,0,0,2,1,1,0,2,2,1,0,1,1,1,1,1,0,0,1,1,2,2,1,0,1,2,1,1,2,1,1,1,0,0,2,1,1,2,0,2,2,0,2,2,2,1,2,0,1,2,0,0,0,0,2,1,1,0,1,1,0,2,0,1,1,0,0,2,0,1,2,1,0,2,1,0,2,1,2,2,0,0,2,0,2,0,0,2,0,0,0,0,2,1,1,2],[0,0,1,1,1,0,0,2,0,2,2,2,1,1,1,0,0,1,1,0,2,1,1,0,1,1,0,0,0,2,2,0,0,2,2,0,1,1,1,1,2,2,0,2,0,0,1,2,2,0,1,1,2,1,2,0,1,2,1,2,2,2,1,1,0,0,0,0,1,0,0,2,1,0,2,0,2,2,0,1,1,2,1,2,1,0,1,1,2,0,0,1,2,2,0,0,0,0,1,2,1,1,1,1,2,1,2,1,0,2,1,1,0,0,2,1,1,1,1,1,0,0,1,0,0,0,1,1,0,2,0,2,1],[2,2,1,1,2,2,2,1,0,0,2,2,0,2,0,1,0,1,0,2,1,2,1,1,0,1,2,1,2,2,1,2,1,2,0,2,1,2,2,1,0,0,0,0,1,0,0,1,2,2,1,0,0,0,2,2,2,1,1,2,0,0,0,2,0,2,1,2,0,1,2,1,0,1,2,2,1,1,1,0,1,0,0,2,2,1,0,2,0,1,0,2,2,1,0,2,0,0,2,0,2,2,1,2,1,2,0,1,2,0,0,0,2,1,0,0,1,2,2,1,2,1,0,2,1,1,0,1,0,2,2,2,1],[2,2,2,2,0,2,2,0,1,2,2,0,1,1,2,1,2,0,1,2,2,1,1,1,0,2,0,2,0,2,1,1,2,1,2,0,1,2,2,1,1,1,1,0,1,2,2,2,1,2,2,1,2,0,2,0,2,2,1,2,2,1,2,0,0,1,1,2,2,1,1,2,0,0,0,2,2,0,1,0,2,2,1,0,0,1,0,1,1,0,2,2,2,1,0,0,1,0,2,2,2,0,2,0,0,2,0,0,0,2,2,0,2,1,1,0,1,2,2,2,0,2,0,0,2,1,2,0,1,1,2,2,1],[0,2,2,2,1,2,2,2,2,2,0,0,1,1,0,0,1,1,2,1,2,1,0,2,1,2,0,2,0,1,0,0,2,1,1,1,2,2,1,0,0,2,2,1,2,1,0,2,1,2,1,2,0,1,2,2,1,0,2,2,0,1,0,2,2,0,1,1,2,2,2,1,1,1,0,2,1,2,1,2,1,0,0,1,2,0,1,0,2,1,1,1,0,0,1,1,0,0,2,2,0,2,0,0,2,2,1,2,2,0,0,1,0,1,0,0,0,1,0,0,2,2,2,2,2,1,1,0,1,1,2,0,1],[0,1,1,1,1,0,0,0,0,2,0,2,0,0,1,1,2,2,1,2,1,0,0,0,1,0,0,1,2,1,0,0,2,2,0,0,0,2,2,0,1,2,1,2,1,0,0,0,2,0,0,0,1,2,0,0,2,2,2,1,1,1,0,0,2,2,2,0,0,2,0,2,0,0,1,2,2,2,1,2,0,0,2,0,1,0,1,1,0,0,0,1,1,0,1,1,1,2,2,1,2,2,1,2,1,2,1,0,2,1,0,1,2,0,0,1,0,2,1,1,2,1,1,1,2,2,0,2,0,1,0,1,0],[1,1,1,1,2,1,1,0,0,1,1,1,0,0,0,1,0,0,1,2,2,1,2,1,0,1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,2,1,1,1,2,1,0,1,1,1,0,1,0,0,0,2,0,1,2,2,2,1,2,0,0,1,2,1,1,0,0,2,1,1,0,2,0,2,2,0,0,0,2,2,0,1,0,2,1,1,2,0,1,2,1,2,1,1,2,1,1,1,2,0,2,0,0,1,2,0,1,0,0,2,0,1,0,1,2,1,0,1,0,1,2,0,0,1,0,0,0,1,1],[2,2,0,1,1,2,2,2,2,0,0,0,0,1,1,2,1,2,2,2,2,2,2,0,0,0,2,0,0,0,0,1,2,0,0,1,2,2,2,0,1,2,1,2,0,2,1,0,2,2,2,0,0,2,0,2,2,1,0,2,1,0,2,1,2,1,2,0,0,2,0,2,0,2,2,2,1,2,1,1,2,1,0,2,1,0,1,2,2,0,0,2,2,1,2,2,0,2,0,0,2,1,2,0,2,2,1,0,0,0,1,2,2,2,1,2,1,1,0,1,0,0,1,1,0,2,0,2,1,2,2,2,2],[2,1,1,0,0,1,0,2,2,0,2,0,0,2,0,1,1,0,1,1,1,0,2,1,2,1,2,0,0,2,1,1,0,1,0,2,2,2,2,1,1,2,2,1,1,1,1,1,1,0,1,2,1,2,0,0,0,0,0,2,0,2,2,2,0,0,1,2,1,0,0,0,2,0,2,1,1,1,1,1,1,1,2,2,2,0,0,1,2,2,0,0,0,0,0,2,1,1,1,1,1,2,0,2,0,2,0,2,2,0,0,1,1,2,2,0,2,0,1,1,1,2,1,0,2,2,1,2,0,1,1,1,1],[1,2,0,1,2,0,1,2,2,1,0,1,1,1,1,1,0,0,2,2,1,0,0,0,0,2,1,0,2,2,0,1,0,2,2,1,0,0,2,2,2,1,1,0,1,0,2,2,0,2,2,2,1,0,0,1,2,0,2,2,1,1,2,0,2,0,1,0,0,0,2,1,2,0,0,1,0,2,2,2,1,2,0,2,1,0,1,0,1,2,0,1,1,0,1,2,0,0,0,0,0,1,0,1,0,0,2,1,2,1,0,0,2,1,0,1,1,0,0,0,1,0,2,1,1,0,0,2,2,0,1,0,1],[2,0,1,0,2,0,2,2,0,1,1,2,0,2,0,2,2,1,1,2,1,1,1,0,1,2,1,1,2,2,2,0,0,1,1,2,0,0,0,0,1,2,2,1,1,1,2,1,0,2,2,0,0,1,0,1,2,2,1,1,0,1,1,0,1,0,0,0,1,0,1,1,1,2,1,0,2,1,2,1,2,2,0,0,1,0,0,1,2,0,1,2,2,2,0,0,2,0,0,1,0,0,2,2,1,0,1,0,2,0,1,2,1,2,2,1,0,2,1,2,1,2,2,1,0,2,0,2,2,2,0,2,0],[2,1,0,1,0,2,1,0,2,2,1,2,1,2,2,2,0,1,1,1,0,1,1,2,1,1,2,1,1,1,0,1,1,1,0,1,2,2,0,0,1,0,0,0,0,2,2,0,2,1,0,0,2,2,1,1,2,0,2,2,1,0,1,2,0,0,0,1,0,1,0,1,1,2,2,0,0,1,1,2,2,2,0,2,1,2,2,0,1,1,1,0,1,1,0,0,1,0,1,2,2,2,2,0,0,2,2,0,0,2,1,1,1,0,2,0,0,2,2,2,2,2,1,2,2,1,0,2,2,0,2,0,2],[1,2,0,2,2,0,2,2,0,2,2,0,0,0,2,1,1,0,0,2,1,2,1,2,2,0,1,1,1,2,1,1,1,2,2,0,0,0,0,1,1,0,2,2,2,2,0,2,2,2,1,2,2,1,0,0,2,1,0,1,0,0,1,2,0,0,0,0,1,1,2,0,2,1,2,0,1,1,0,1,0,0,1,0,1,2,1,2,0,2,2,2,2,0,0,2,0,1,2,2,1,2,0,2,0,2,2,1,1,1,1,2,2,0,0,1,0,2,0,1,1,1,2,1,1,0,0,2,0,0,2,2,1],[2,1,1,0,0,2,2,2,0,1,2,1,0,0,2,1,0,2,0,0,0,1,1,1,2,0,1,2,2,2,0,2,1,0,2,1,0,1,0,0,2,0,1,0,1,1,0,1,2,0,1,0,2,2,0,1,0,0,1,1,0,0,0,1,2,0,2,2,1,0,0,0,0,2,2,2,1,1,0,1,0,1,0,1,0,2,2,1,2,0,1,1,0,2,2,1,1,2,2,2,2,0,1,0,2,1,1,1,0,2,2,1,0,0,0,0,2,0,0,2,2,0,2,0,1,2,0,0,2,1,2,2,2],[0,1,1,0,1,0,0,2,0,1,1,2,0,1,2,0,1,1,1,0,1,1,2,1,0,0,1,2,0,2,0,1,0,1,1,0,0,0,1,1,2,0,0,2,1,0,0,1,1,0,2,2,1,2,0,0,0,0,1,1,2,2,1,1,0,1,0,0,0,0,2,1,2,2,1,0,1,0,0,0,2,1,2,1,2,2,1,0,0,2,0,0,0,1,1,1,0,2,1,1,2,2,1,1,0,1,2,0,0,2,2,2,0,0,1,2,2,0,0,0,0,1,0,0,0,2,2,0,1,1,0,0,1],[2,1,0,0,2,1,2,1,0,0,1,1,2,1,2,2,1,2,2,2,1,0,2,0,2,0,2,0,2,0,2,1,1,2,2,2,1,2,0,1,2,2,0,0,0,1,0,0,0,2,1,2,2,2,1,0,2,2,1,1,0,2,2,2,2,0,2,0,2,0,0,0,2,0,2,1,0,1,2,0,0,0,2,0,0,2,0,2,2,1,2,2,1,1,1,0,0,1,1,2,0,0,1,2,2,0,2,2,0,1,1,0,0,1,0,0,2,1,1,0,2,2,0,0,0,0,1,1,2,2,2,1,2],[2,2,1,1,2,0,2,0,1,1,0,1,1,1,1,1,0,0,1,0,1,1,2,0,0,2,0,0,1,1,0,1,0,0,0,0,1,1,2,2,1,0,2,2,2,2,0,2,0,1,2,2,1,1,2,0,1,0,1,1,1,1,2,2,2,0,2,0,1,2,0,0,2,1,2,2,0,1,1,0,2,1,1,2,1,0,0,1,1,0,2,2,2,0,2,0,1,0,1,0,2,1,2,1,0,0,1,1,2,1,2,2,1,2,0,1,0,0,2,0,0,1,0,0,0,0,2,1,0,2,1,1,0],[1,2,1,0,2,0,1,1,0,0,1,1,1,2,2,2,1,0,2,0,1,1,0,0,0,0,1,2,0,2,2,0,1,2,1,1,1,2,2,2,1,1,0,2,0,2,2,2,2,0,2,0,1,2,1,2,1,2,2,0,0,2,0,2,1,1,0,0,0,1,1,2,1,2,0,2,1,2,2,0,2,1,1,0,2,2,2,0,1,1,2,0,2,0,0,0,1,2,1,0,2,2,2,1,0,2,0,2,0,2,0,0,1,0,2,1,0,0,2,0,0,1,1,0,0,0,0,1,1,0,2,1,0],[0,0,0,0,2,2,1,0,1,2,2,2,1,0,0,1,1,2,2,1,2,0,2,1,2,2,1,1,0,0,2,2,2,0,0,1,0,2,2,2,2,0,1,2,0,0,0,0,0,1,1,1,1,0,1,2,0,1,1,1,2,0,1,1,1,1,0,1,2,0,2,0,1,0,0,0,2,2,2,1,0,0,1,1,2,1,0,2,1,1,2,0,1,2,2,1,0,0,0,2,0,2,2,0,0,1,1,1,2,2,2,1,0,1,2,1,1,0,1,0,2,0,1,0,1,0,1,2,0,1,0,1,1],[0,2,0,2,0,1,0,0,0,1,0,1,2,1,2,2,2,2,0,0,1,1,1,0,2,0,1,2,1,1,0,1,1,2,1,2,2,2,2,1,0,0,1,0,2,2,2,2,0,2,0,2,0,2,0,2,0,2,2,2,2,1,0,2,2,1,1,1,1,2,0,1,2,1,2,2,0,2,2,2,2,2,1,2,2,1,0,1,1,2,1,0,0,0,2,0,0,2,2,2,0,0,1,1,1,1,0,1,0,0,2,0,2,1,2,1,0,0,2,0,1,1,1,1,0,1,2,0,1,2,1,1,2],[0,2,2,2,2,1,0,1,0,2,0,2,1,0,2,2,0,2,0,0,2,0,2,0,2,1,0,0,0,0,0,0,1,2,1,0,0,1,2,1,0,2,0,0,1,1,2,1,0,0,0,0,1,1,2,0,2,2,2,1,2,2,2,0,2,0,1,1,0,2,1,1,1,1,2,0,2,1,0,1,2,1,0,0,1,0,0,0,2,1,0,2,1,0,0,0,0,2,0,0,0,1,2,1,1,1,1,1,0,2,1,2,2,0,2,0,2,1,0,1,1,0,2,0,0,0,1,0,2,0,1,1,1],[2,1,2,1,0,1,2,1,2,1,0,2,2,2,1,0,1,1,2,0,1,1,1,1,1,0,1,2,2,0,2,2,0,2,1,2,0,1,0,2,2,2,1,1,2,2,1,1,1,0,0,0,0,2,0,2,1,0,2,0,0,2,1,0,2,1,1,2,1,0,2,1,2,0,2,1,2,2,2,0,2,1,1,1,0,0,0,2,1,0,0,1,0,1,1,2,0,2,0,1,1,2,2,1,0,1,0,2,2,2,2,1,1,2,0,2,1,1,2,2,0,0,0,1,2,1,1,2,2,0,1,1,0],[1,0,1,0,1,2,0,1,0,2,0,1,2,1,2,2,2,2,2,2,2,1,1,2,1,0,1,2,0,2,2,1,0,0,2,0,0,0,2,2,2,2,2,0,1,0,2,2,0,2,1,0,1,2,1,2,2,2,0,2,0,1,2,0,0,0,1,0,2,2,2,0,2,0,2,1,2,1,2,1,2,0,1,1,1,1,0,2,1,2,2,0,0,1,0,2,1,0,0,0,1,0,1,0,1,2,1,1,2,1,0,2,0,0,0,0,2,2,2,2,2,2,1,0,2,0,2,1,2,2,2,2,0],[0,0,1,1,2,1,1,1,0,2,2,2,2,2,2,1,1,0,1,2,1,2,1,2,1,2,2,2,1,1,0,1,1,2,1,0,0,0,1,2,2,1,0,2,0,1,2,1,0,1,1,0,2,2,2,0,1,1,0,0,0,2,2,0,2,0,2,0,1,2,2,2,0,2,0,1,1,1,0,2,0,1,0,0,2,2,2,1,0,1,0,2,2,0,1,1,0,0,2,1,1,1,1,1,2,2,0,1,2,2,2,2,2,2,1,1,0,0,1,0,1,1,1,0,0,0,0,1,0,2,0,0,0],[2,2,0,2,1,0,2,1,2,0,1,0,1,2,1,0,1,0,1,1,2,1,0,1,2,0,0,1,2,2,0,1,0,2,1,1,1,2,1,2,2,2,2,1,2,0,0,1,1,0,0,1,1,0,1,1,0,2,2,0,0,1,0,2,1,1,0,2,0,0,0,0,0,2,1,0,2,0,2,2,2,0,1,0,1,0,2,0,2,0,1,0,0,2,2,2,0,0,0,1,2,0,2,1,2,0,0,1,2,2,0,0,2,2,1,0,0,0,0,2,2,0,0,0,2,2,0,2,2,1,1,2,0],[0,2,0,1,1,1,2,1,1,1,1,0,2,0,1,0,0,1,0,1,1,2,2,0,1,1,2,0,2,0,1,2,0,0,0,1,0,0,2,2,1,2,0,2,0,2,1,0,0,2,2,1,0,0,1,0,0,0,1,0,0,1,1,0,1,0,2,2,2,1,2,1,2,2,1,1,0,0,0,0,0,2,2,1,1,2,1,2,2,1,2,1,0,2,1,2,1,1,0,0,0,0,1,2,0,1,1,0,0,0,2,1,0,2,2,0,0,0,2,2,1,1,1,1,1,0,1,0,2,1,0,2,1],[2,2,1,0,0,0,2,2,1,2,0,0,0,2,1,1,0,1,1,1,2,0,0,1,1,1,1,2,1,1,0,2,2,1,1,2,0,1,1,1,2,1,1,1,0,1,1,1,0,0,2,2,2,1,2,2,1,1,0,2,0,1,0,1,2,2,0,0,1,2,1,1,1,2,2,2,1,1,2,0,2,2,0,2,2,0,0,1,1,1,0,2,1,1,0,2,0,0,2,0,0,0,2,2,1,1,1,2,1,1,1,0,1,0,2,1,1,0,1,0,1,2,0,2,1,2,1,2,2,0,0,2,2],[0,1,2,0,1,2,1,1,0,2,2,1,2,1,0,2,2,2,1,1,2,1,1,2,1,2,1,0,0,2,0,1,0,1,2,0,0,2,0,2,1,1,2,2,0,2,1,2,1,1,2,0,1,2,1,1,0,2,1,1,0,1,1,1,1,1,2,1,1,0,1,1,0,0,0,0,1,1,0,1,0,2,1,1,2,1,0,2,1,0,2,0,2,1,2,0,2,0,0,2,2,2,2,2,2,0,2,2,1,1,0,2,2,0,0,1,1,2,2,2,1,1,1,2,1,1,2,2,0,1,0,0,1],[1,2,2,1,1,1,2,2,0,2,2,2,2,0,1,2,1,2,2,2,1,0,2,0,2,1,1,2,0,2,0,2,0,1,2,2,2,1,2,1,0,2,2,1,0,1,0,2,2,2,1,0,2,0,2,2,2,2,0,2,0,2,2,0,0,0,0,1,2,1,1,1,2,0,0,0,0,0,1,2,2,2,2,2,0,2,1,0,2,2,2,0,1,0,2,2,1,2,1,1,2,0,1,1,1,1,2,0,1,1,1,0,0,2,0,1,0,0,1,0,0,0,0,0,2,0,0,2,1,2,1,2,2],[0,1,0,2,2,1,1,2,0,2,2,1,1,1,0,0,0,0,0,2,1,0,0,2,0,1,1,1,2,0,2,0,1,1,0,1,1,1,2,1,0,2,0,2,0,1,1,2,0,1,1,0,1,1,1,0,2,1,0,0,0,0,0,2,1,0,0,2,2,0,2,2,1,0,1,0,0,2,2,2,2,0,2,2,2,2,2,1,2,1,1,0,2,0,0,0,0,0,1,2,1,1,0,2,2,2,2,1,2,2,0,2,1,1,0,2,0,2,2,2,0,0,2,1,2,2,1,2,0,0,0,2,2],[1,2,0,0,2,0,2,0,0,0,1,1,2,2,0,1,2,1,2,0,0,0,2,0,0,1,0,1,0,0,0,2,1,2,2,0,1,1,0,2,2,2,1,1,1,0,2,2,1,0,0,1,1,0,2,2,1,0,0,2,0,0,2,2,2,1,0,1,1,2,2,0,1,0,1,2,0,2,2,2,2,1,1,2,2,2,0,1,2,2,2,2,1,1,0,0,1,0,1,1,1,1,1,1,0,1,1,0,2,1,2,2,0,0,0,1,0,1,1,1,2,0,2,1,0,0,2,1,0,0,1,0,1],[1,1,2,2,0,2,2,1,0,0,2,0,1,1,1,2,0,2,2,2,0,2,2,1,0,2,1,1,2,2,0,1,0,2,2,1,2,1,0,2,1,2,1,1,1,1,1,2,0,2,0,1,0,2,0,0,1,2,2,2,0,2,2,2,2,2,2,0,2,1,1,2,0,0,0,0,2,0,2,0,0,2,2,2,2,1,1,2,0,2,0,1,0,1,1,1,2,2,0,1,2,1,0,2,0,1,1,2,1,1,1,0,2,1,1,2,0,0,1,0,1,2,2,2,1,0,1,2,0,0,2,2,0],[2,2,2,1,2,0,2,0,2,2,1,0,1,1,1,2,2,0,1,1,1,2,0,2,2,2,0,2,1,2,1,2,1,2,0,2,2,1,1,0,1,2,0,1,0,2,0,0,1,2,0,2,2,0,2,1,0,2,2,1,0,0,0,1,2,2,1,0,1,2,2,2,1,0,0,1,2,2,1,1,1,1,2,2,1,0,0,1,1,2,1,1,1,1,1,2,0,2,2,0,2,1,1,0,0,0,0,0,1,1,0,0,1,2,0,2,0,1,0,1,1,0,2,2,0,0,0,1,2,0,2,1,2],[1,2,2,2,1,2,0,2,2,1,0,1,0,2,1,0,2,2,1,2,2,0,0,1,0,2,2,2,0,0,2,0,1,2,1,2,0,0,2,0,1,2,1,2,1,0,2,2,2,1,2,1,0,0,0,1,2,0,1,2,1,1,1,2,1,2,0,2,0,0,0,1,2,2,2,2,1,0,2,0,0,1,1,1,2,2,0,1,1,1,1,2,2,1,0,2,2,0,0,1,1,0,1,0,1,2,0,0,0,1,1,0,0,0,0,1,0,1,0,0,1,2,2,1,1,0,2,0,2,1,2,0,1],[1,0,0,1,1,2,2,2,1,0,1,0,2,0,2,0,2,1,2,2,0,0,1,1,2,0,0,1,0,2,2,1,1,2,2,1,0,0,0,1,1,0,1,1,0,0,1,0,2,2,2,0,1,2,0,2,1,2,1,0,1,0,0,2,1,2,0,2,1,0,0,1,1,1,1,0,2,0,2,1,1,0,2,1,0,0,0,2,1,2,1,0,2,2,1,1,1,1,2,0,1,2,2,0,2,0,0,0,0,0,2,1,0,1,1,2,0,0,2,1,2,1,1,1,0,2,0,2,2,1,1,1,1],[1,1,0,0,1,1,0,0,2,1,1,1,1,2,0,1,1,2,2,1,2,1,1,2,1,0,0,2,1,0,0,0,0,2,0,0,0,2,1,1,0,0,0,1,2,1,0,2,0,1,0,1,0,2,0,2,0,1,0,2,2,2,2,1,0,0,0,1,0,2,2,1,1,0,1,1,1,2,0,0,1,2,0,0,1,0,2,1,1,0,2,1,0,0,1,1,2,2,2,2,0,0,2,2,2,1,2,2,1,1,1,0,2,2,2,2,2,2,2,0,2,1,0,2,1,2,0,2,1,0,2,2,0],[2,1,0,0,0,2,0,0,1,0,0,2,1,2,2,2,1,2,2,1,1,0,1,2,1,2,2,1,1,1,2,0,0,2,1,2,1,1,0,1,1,1,0,0,2,1,0,0,0,0,0,1,1,0,1,2,2,0,2,1,2,2,1,0,1,2,2,1,1,0,0,2,2,0,0,0,0,1,1,1,0,1,0,1,0,0,2,0,0,1,0,2,1,1,1,2,2,0,2,0,2,2,0,1,1,2,0,2,0,1,1,2,2,0,0,1,2,2,1,0,0,1,2,0,2,1,2,1,2,0,2,2,0],[2,0,1,1,1,1,2,1,1,2,1,1,0,0,0,1,2,2,1,0,2,1,1,1,2,0,2,2,2,0,1,0,0,2,1,0,0,2,2,0,2,1,0,0,2,0,1,2,2,2,2,0,1,0,0,2,2,0,2,0,2,1,1,0,0,2,1,2,0,1,1,1,0,0,1,2,2,0,0,0,2,1,2,0,0,0,1,0,2,1,0,2,2,1,2,0,1,0,2,0,2,2,0,2,1,0,2,1,0,2,1,0,2,0,1,0,0,1,2,1,1,0,0,2,1,2,1,0,1,0,0,2,0],[0,0,1,2,2,2,2,2,1,1,0,0,0,2,1,1,0,0,0,2,0,1,1,0,2,2,2,0,1,1,2,1,0,1,0,0,2,1,1,0,1,2,1,2,1,2,2,1,1,0,2,0,0,0,1,0,1,2,1,1,1,0,0,1,1,0,1,2,0,2,0,0,0,2,1,0,2,2,0,1,0,1,2,2,0,1,0,1,2,1,1,1,0,2,1,2,0,2,2,0,2,0,1,2,1,0,2,1,1,1,2,1,2,2,0,1,1,1,1,1,1,1,0,1,0,0,2,1,1,2,2,2,2],[0,0,0,0,2,0,1,0,1,0,0,2,2,0,2,2,1,1,0,2,2,1,0,2,2,2,2,0,1,1,0,0,0,2,1,1,2,1,1,1,1,0,0,1,0,1,0,2,2,0,1,1,2,1,1,0,2,1,0,1,0,2,1,0,0,0,0,0,0,0,0,1,1,2,0,0,1,0,0,2,1,2,1,0,0,1,2,1,2,0,0,1,0,1,2,0,0,0,1,0,0,0,1,2,2,0,0,1,2,0,2,1,1,2,0,2,1,1,2,1,0,0,0,2,0,1,1,2,2,0,0,1,0],[1,0,2,2,1,0,1,1,2,1,0,2,1,2,2,2,0,1,1,2,2,0,1,0,2,1,1,0,2,0,2,0,1,2,2,1,1,2,2,1,0,0,0,1,0,2,1,1,0,1,1,2,0,0,1,0,2,1,2,2,0,0,2,2,2,1,1,1,0,1,2,0,2,2,2,2,0,2,0,1,2,0,2,2,0,1,0,2,0,0,2,0,0,0,2,2,2,1,1,1,2,2,0,1,2,1,0,2,1,2,0,1,0,0,1,2,0,1,2,1,0,2,0,2,2,2,0,1,1,0,0,2,1],[1,2,1,0,2,2,2,0,1,2,1,1,1,0,0,1,1,1,1,0,1,0,1,1,1,2,2,0,2,0,2,0,0,2,1,0,0,2,1,0,1,1,2,0,2,0,0,2,1,2,2,2,2,1,0,2,0,2,1,1,1,1,1,0,1,0,1,1,2,1,2,0,1,2,0,2,2,2,2,1,2,2,2,0,2,0,0,2,2,1,0,2,2,1,0,0,1,1,0,1,1,1,1,1,0,0,2,2,1,2,1,2,0,1,0,2,0,0,2,1,2,1,2,2,0,1,1,0,0,2,0,2,2],[0,1,2,0,1,2,0,0,1,1,2,1,0,0,1,0,2,1,2,1,2,2,1,1,1,2,2,0,0,1,2,1,1,0,2,0,2,2,2,0,1,0,0,1,1,2,2,1,1,0,1,2,2,0,2,2,2,0,1,2,2,0,0,0,1,1,2,2,2,2,2,0,1,0,2,2,2,0,2,2,0,1,1,0,0,0,2,2,1,1,0,1,0,2,2,2,0,2,2,2,1,0,1,2,1,0,2,1,0,2,1,2,2,2,0,1,0,0,0,0,0,1,2,1,0,1,2,0,2,1,1,2,1],[0,2,1,1,0,0,2,1,2,1,1,2,1,0,2,1,1,2,1,1,1,0,2,0,0,1,2,1,1,0,1,0,1,1,0,1,2,0,2,1,1,1,0,1,2,0,2,2,1,2,0,0,1,1,2,0,1,0,0,1,1,1,0,0,1,0,1,0,2,1,1,2,2,1,0,1,2,2,2,1,1,2,0,1,0,0,0,0,1,0,2,2,1,2,1,2,2,0,2,2,1,0,0,2,2,2,1,0,0,1,2,0,2,0,1,2,0,0,0,0,2,2,0,1,1,1,2,2,0,0,1,1,2],[0,0,2,2,0,1,0,0,0,0,0,1,2,0,1,2,2,1,2,2,0,1,1,2,2,1,1,0,0,0,2,0,0,0,1,1,0,0,2,0,1,0,0,1,2,1,0,1,2,2,0,1,2,1,1,1,1,0,0,1,2,2,1,1,0,2,2,2,2,0,0,2,0,1,1,1,1,1,1,2,2,0,2,2,2,0,2,2,1,0,2,2,2,0,2,0,2,0,1,2,2,0,0,2,0,0,1,0,0,0,0,2,0,1,2,0,1,0,0,1,2,0,0,2,1,1,0,1,2,2,0,1,2],[2,2,0,1,1,0,2,0,2,0,2,2,0,1,0,2,0,2,2,0,2,0,0,1,0,0,2,2,2,0,1,2,0,1,0,0,2,2,1,2,1,1,1,0,2,2,0,2,2,1,2,1,0,1,2,0,2,0,0,2,0,1,0,0,2,0,1,1,0,0,2,1,0,1,1,2,2,2,1,0,0,2,2,0,1,2,2,2,1,0,1,0,1,0,0,2,0,0,2,0,1,2,0,0,0,0,2,1,2,2,0,0,1,0,0,0,0,0,2,1,2,0,2,0,0,1,0,2,2,0,0,0,2],[1,0,2,2,2,2,1,2,1,2,0,2,1,1,2,0,2,1,1,1,0,2,2,1,0,1,0,1,0,1,2,1,1,1,0,0,2,1,2,0,1,1,0,1,2,2,2,0,2,2,1,0,0,2,1,1,1,2,2,0,2,2,0,1,1,2,2,0,2,1,0,1,2,2,1,2,1,1,2,1,0,0,1,1,0,1,1,0,1,1,2,2,0,0,1,0,0,0,2,1,2,0,2,0,0,0,0,2,0,1,2,0,2,2,1,2,1,1,2,2,2,1,1,1,0,1,1,1,2,2,0,1,1],[2,1,2,0,0,1,1,0,0,1,0,1,0,2,0,0,2,0,2,2,1,1,1,2,2,2,2,1,1,2,1,0,1,0,0,1,1,1,0,1,2,0,2,1,1,1,0,1,1,1,1,2,0,2,2,0,2,2,1,1,0,1,0,0,2,0,0,0,1,2,2,2,1,0,1,2,1,1,1,1,1,0,2,0,2,0,2,0,2,2,1,0,1,1,1,0,0,2,1,0,1,0,1,0,2,1,0,0,0,1,0,2,2,0,1,0,0,0,1,2,1,1,2,1,2,2,1,2,2,0,1,1,1],[2,1,0,1,1,0,0,2,0,0,1,0,2,2,0,0,0,0,1,2,2,1,1,1,2,2,0,1,2,0,1,1,0,2,1,1,0,0,2,0,1,1,1,1,0,1,1,2,2,0,2,0,0,1,2,1,1,0,1,2,0,2,1,2,0,2,2,0,0,2,2,0,2,0,1,2,2,0,2,2,2,1,2,1,1,1,1,0,1,2,2,0,1,1,1,0,1,0,0,2,0,1,0,0,1,2,1,2,0,2,1,1,2,0,2,1,1,2,0,0,1,0,2,1,1,1,1,0,2,2,0,2,0],[1,2,1,2,0,0,2,0,1,1,2,0,2,2,2,2,1,0,1,1,1,0,0,2,0,2,2,0,2,2,2,0,1,2,2,1,0,0,0,2,0,2,0,2,2,0,1,1,1,1,1,0,2,1,1,1,0,0,0,2,2,0,2,2,0,2,1,0,2,1,1,1,0,2,0,2,2,0,2,0,2,0,0,2,2,2,2,1,1,2,0,2,0,1,2,1,0,1,0,2,1,1,1,2,2,2,0,1,0,1,0,2,0,0,2,1,0,2,0,0,1,0,1,0,0,0,0,2,0,1,0,1,2],[2,2,1,2,1,2,0,2,1,2,1,0,2,2,1,1,2,1,2,1,2,2,1,0,1,2,1,0,1,2,0,2,1,0,0,1,2,2,1,0,0,2,1,1,1,1,2,2,2,1,2,1,1,0,2,0,2,0,2,1,2,2,2,1,2,1,0,0,2,0,0,2,1,0,2,1,0,0,0,2,2,1,1,2,2,0,0,1,1,0,1,2,1,2,2,1,1,0,0,1,0,0,0,2,1,2,2,0,0,1,0,1,1,1,2,1,2,0,1,1,1,1,0,0,2,0,0,2,2,1,2,2,0],[1,1,2,2,1,0,2,0,2,2,2,2,0,0,1,0,2,1,2,0,0,1,0,0,2,0,0,0,1,0,2,1,0,1,1,1,1,1,0,0,1,2,2,0,0,1,2,0,1,0,2,0,1,1,1,1,1,1,2,1,2,2,1,0,0,2,0,2,1,2,2,0,0,1,2,0,0,1,1,1,2,0,1,0,1,2,0,0,0,1,2,2,1,0,1,1,0,0,0,1,2,0,2,1,1,1,0,1,1,1,0,2,0,1,1,0,2,0,2,1,1,0,1,1,2,0,1,0,2,1,0,2,1],[0,0,0,2,2,2,1,0,2,1,1,1,1,2,2,2,1,0,1,1,2,0,0,0,1,2,0,0,2,1,1,1,1,2,0,0,0,1,1,0,1,1,2,2,2,0,2,0,2,1,0,0,1,0,1,0,1,1,2,2,0,1,1,0,1,2,1,1,1,0,1,1,2,1,2,1,0,2,1,1,1,0,1,2,1,1,1,0,0,2,2,0,2,2,0,2,2,1,0,0,1,2,1,0,2,1,2,2,2,0,0,0,0,2,1,2,2,1,2,1,2,2,1,0,2,1,0,0,2,2,2,0,2],[0,1,0,1,2,2,0,2,2,1,0,2,1,2,0,2,0,2,2,0,0,1,2,0,0,0,2,0,1,2,2,2,1,0,2,0,0,2,2,0,2,0,1,2,1,1,0,2,2,0,1,2,0,0,2,2,2,2,0,2,2,2,1,0,2,1,2,1,2,0,2,0,2,0,2,0,1,1,1,0,0,2,1,2,2,2,1,2,0,1,2,2,0,2,2,0,2,1,0,2,0,1,1,0,1,2,0,0,2,0,0,0,0,1,0,0,0,0,0,1,2,0,1,2,2,0,0,0,0,1,1,0,0],[0,0,2,0,0,2,0,0,1,0,1,0,0,0,1,2,0,2,0,2,1,1,2,0,1,2,2,2,2,2,2,0,2,0,1,0,0,0,2,1,0,1,2,2,0,1,2,2,0,0,2,0,0,1,0,1,2,2,0,0,1,1,0,2,0,1,2,0,2,0,2,0,0,2,0,2,1,2,1,2,0,1,2,2,0,0,1,1,2,0,2,2,2,1,2,2,0,1,2,2,1,1,1,0,1,0,1,1,0,2,2,0,2,0,0,2,1,2,1,1,0,1,1,0,1,1,1,0,1,1,0,0,1],[1,1,1,1,2,2,2,2,1,1,1,1,2,0,0,2,1,2,2,1,1,1,1,2,2,0,2,0,0,2,2,1,0,0,0,1,2,0,0,1,1,0,2,0,0,0,2,2,0,0,2,0,0,1,1,0,1,2,0,1,0,1,1,2,2,0,2,2,2,2,0,0,1,0,0,1,1,2,1,0,1,1,1,1,0,0,1,0,2,1,2,0,2,1,2,1,2,0,2,0,0,1,2,1,0,2,0,1,1,0,0,2,0,1,1,2,1,2,1,2,2,0,2,2,1,2,1,0,2,2,1,1,0],[0,2,1,0,1,1,1,0,2,2,2,2,0,1,1,0,1,2,2,1,0,2,0,1,1,0,2,0,0,2,2,0,0,2,1,2,2,1,0,1,0,1,2,0,1,1,2,0,1,1,1,1,1,0,0,0,1,1,2,0,1,2,0,1,2,0,2,2,2,2,2,0,2,2,0,1,1,0,1,0,0,0,1,0,0,2,1,2,2,1,2,0,2,1,1,2,2,0,1,0,0,2,1,0,0,2,0,1,2,2,0,0,2,2,0,1,1,2,2,0,1,2,1,1,2,2,1,1,1,1,0,0,1],[0,1,0,0,1,0,2,2,2,1,2,1,2,0,1,2,1,2,0,1,1,1,2,0,0,0,1,1,2,1,2,2,0,0,1,2,0,2,0,1,1,2,2,0,0,2,0,2,1,0,2,1,1,2,2,2,1,2,0,1,2,0,0,0,1,1,2,2,0,0,2,1,1,2,2,1,0,2,1,0,0,0,1,0,0,2,1,2,2,1,1,1,2,0,2,0,2,2,0,1,2,1,1,0,1,1,1,2,1,2,2,1,1,0,1,0,0,2,0,0,1,0,2,0,1,0,0,2,1,0,2,1,2],[1,0,0,0,2,0,2,2,1,1,2,1,2,1,0,1,0,0,2,2,1,0,1,0,0,2,2,1,1,0,1,0,2,2,0,1,0,2,0,2,2,0,0,0,0,1,2,1,2,2,2,1,0,2,0,1,1,2,2,1,0,1,1,1,1,1,0,2,0,1,1,1,1,0,0,0,2,0,0,0,1,2,0,0,1,0,2,0,2,1,0,0,1,1,1,1,2,2,0,2,0,0,1,0,2,1,1,2,2,2,0,0,2,1,1,2,0,0,0,2,2,2,2,0,1,0,2,0,1,0,2,0,0],[0,2,1,2,2,1,0,0,1,0,0,1,0,0,2,2,1,1,1,0,2,1,1,2,1,1,1,2,0,2,2,0,2,1,0,0,2,0,1,1,1,2,2,1,0,1,0,1,1,0,2,2,1,0,1,0,0,0,1,0,0,0,0,0,1,0,2,2,2,2,0,2,2,2,0,2,1,2,1,2,0,2,2,2,1,2,2,1,1,1,2,1,0,0,1,1,2,1,1,1,0,0,0,1,0,0,2,1,2,0,2,0,1,2,2,1,1,0,2,1,0,2,1,2,0,2,1,0,2,1,0,0,1],[0,0,1,1,2,1,1,0,2,0,2,0,1,1,1,2,1,2,0,0,1,0,1,0,0,0,1,2,0,2,1,1,1,1,0,2,1,0,0,0,0,2,0,2,0,2,2,0,0,0,1,1,1,0,1,2,1,2,1,1,1,1,1,0,1,0,2,2,1,0,2,2,1,0,2,0,1,0,2,0,0,1,0,1,0,1,1,1,0,1,2,1,1,1,1,0,0,1,0,2,2,1,2,0,0,0,2,1,0,0,0,1,0,2,0,0,0,0,0,1,1,0,1,2,1,2,0,0,0,2,1,0,0],[2,2,2,1,0,0,1,0,0,2,1,1,2,0,1,0,1,0,2,0,1,0,1,1,0,0,0,0,1,2,0,2,2,0,2,1,0,2,0,0,0,0,2,0,1,2,0,1,1,0,1,2,2,1,2,0,0,1,0,2,1,0,0,1,2,2,0,1,2,0,0,1,1,1,0,2,0,1,1,0,1,0,2,0,1,1,1,1,2,1,0,1,1,2,0,2,1,2,1,1,0,0,2,2,2,1,0,0,0,0,0,0,0,2,2,1,2,2,1,2,1,0,2,1,0,1,1,0,2,2,1,2,0],[2,1,1,2,0,0,2,0,2,1,0,1,1,1,2,1,1,0,1,1,2,2,0,2,2,0,2,0,0,1,2,1,1,0,1,2,2,2,0,2,1,0,2,2,2,2,1,1,0,2,1,2,1,1,1,0,1,0,2,1,2,2,1,1,1,1,1,2,2,1,2,0,1,0,2,2,0,0,1,2,0,2,1,1,1,0,0,1,0,0,2,0,1,1,0,1,0,1,0,2,1,0,2,2,0,0,0,0,2,2,0,0,0,0,2,1,1,0,0,0,0,0,2,2,2,0,1,2,2,1,2,0,0],[2,2,1,0,2,0,2,1,2,0,2,2,1,2,2,0,1,1,0,0,0,0,1,2,1,1,1,2,0,1,0,1,2,1,0,1,2,2,1,0,0,2,1,1,2,1,1,2,0,1,1,1,1,0,0,1,2,1,0,2,1,0,2,2,0,0,0,1,2,1,0,0,0,1,1,0,0,2,0,0,0,0,2,0,0,2,0,2,0,1,2,2,2,0,0,2,2,1,1,2,0,2,2,0,2,0,1,0,0,1,0,2,1,1,0,2,1,1,0,0,2,0,1,1,0,0,1,2,2,2,2,2,0],[2,0,0,1,1,0,1,0,1,1,0,2,0,1,2,1,2,0,0,0,1,1,2,1,1,2,1,0,2,2,1,1,1,2,2,0,1,0,2,1,2,1,1,0,2,1,2,1,0,2,2,1,0,1,2,2,2,2,1,2,2,0,0,0,0,2,2,0,2,2,0,0,1,0,0,1,0,2,0,2,2,1,2,2,1,2,1,0,1,1,1,2,0,0,0,0,0,0,0,0,2,2,0,1,2,0,2,2,0,2,1,1,0,1,0,1,1,0,0,2,0,1,2,0,1,0,0,1,2,2,0,2,2],[1,1,2,0,1,0,1,0,1,2,0,2,2,1,0,0,1,0,2,2,2,1,1,2,0,1,2,0,0,2,1,2,1,0,2,1,0,1,0,2,2,0,2,1,1,0,2,1,1,2,0,0,0,1,0,1,1,2,2,0,1,0,1,2,1,2,0,1,1,1,2,0,0,1,0,0,2,1,1,1,0,1,0,2,2,1,2,0,2,2,2,0,2,1,0,1,1,0,0,1,1,0,2,0,2,1,0,1,1,2,2,1,2,0,2,0,2,0,0,2,2,0,1,0,2,1,1,2,1,1,2,1,2],[2,0,1,0,0,0,2,0,1,2,1,0,0,2,2,1,0,0,2,0,1,0,2,0,2,0,0,0,2,2,1,2,0,1,0,0,1,2,1,1,2,2,2,1,2,0,1,2,1,0,1,1,1,0,2,2,0,2,0,2,1,0,0,2,1,1,2,2,2,0,2,0,0,2,1,1,1,1,2,1,2,1,1,2,1,2,0,2,0,1,0,0,1,1,2,1,1,0,0,0,1,0,1,2,2,1,2,1,0,1,1,2,1,2,1,0,0,2,0,1,0,0,0,1,0,2,1,2,1,1,1,0,1],[0,1,1,0,0,0,0,0,0,2,2,1,1,2,2,2,2,1,1,0,2,0,2,1,2,1,0,0,1,1,2,1,2,1,0,2,1,1,2,0,1,0,2,2,0,0,1,0,1,1,1,2,2,2,1,2,1,1,0,0,0,0,1,2,1,1,0,0,0,1,0,0,1,2,1,2,2,0,2,1,1,0,0,2,1,1,0,2,0,1,2,0,2,0,0,1,0,1,0,0,2,1,2,0,2,1,2,0,2,1,0,0,1,2,0,0,1,2,1,2,0,0,2,1,1,2,1,0,2,0,2,2,2],[1,2,2,2,0,1,1,2,1,0,1,1,0,1,0,1,2,2,2,2,0,1,0,2,1,2,2,0,1,2,1,0,1,2,2,0,1,1,2,2,2,2,1,1,1,0,1,2,1,2,2,1,1,1,1,1,0,0,2,0,0,0,2,0,0,0,2,0,2,0,1,1,0,0,1,0,1,2,2,1,0,2,0,1,0,2,2,1,1,1,0,1,2,2,0,0,0,1,1,2,0,0,0,1,1,1,2,0,1,0,0,0,0,2,2,0,2,0,1,0,1,2,0,1,1,2,2,0,0,0,1,2,0],[0,1,0,1,0,2,1,2,2,2,1,0,1,0,2,1,2,0,1,2,2,1,2,0,1,2,2,0,2,1,1,2,1,2,2,1,1,1,1,1,2,1,2,2,2,0,2,2,2,0,0,2,0,2,1,2,2,0,2,0,0,2,2,0,0,0,0,0,1,2,0,2,2,0,2,2,0,1,2,0,0,0,0,2,0,0,1,0,2,2,1,2,2,1,2,1,0,2,2,2,1,2,0,2,0,0,0,0,2,1,2,1,0,1,1,1,2,2,0,1,2,2,2,2,1,0,2,0,0,1,1,1,1],[0,0,1,2,2,1,1,2,0,1,0,2,0,2,2,0,2,0,2,1,0,2,1,0,1,0,2,2,1,1,2,2,1,1,2,2,0,1,0,0,1,1,0,2,1,2,2,1,2,1,2,2,0,2,2,2,2,1,1,0,1,0,1,2,2,0,1,2,1,1,2,2,0,2,1,2,2,0,2,0,0,1,1,2,2,1,2,2,1,1,1,1,2,1,0,0,2,2,2,0,0,1,2,1,0,2,0,2,2,1,0,0,1,2,0,2,2,1,2,2,0,2,0,2,0,0,2,1,2,2,2,1,1],[1,0,2,2,1,2,0,2,0,1,2,1,2,2,2,2,0,1,0,2,0,2,1,2,2,0,0,0,2,2,0,0,0,1,0,0,0,1,2,0,0,2,2,2,0,1,1,0,2,0,1,1,0,1,2,2,1,0,1,1,0,2,2,1,2,0,1,2,2,2,2,1,2,1,0,0,1,1,2,1,1,0,2,2,2,0,0,0,1,1,2,0,1,1,1,2,0,0,1,2,1,2,0,1,2,1,1,0,1,0,1,0,0,2,1,0,0,0,2,0,1,1,0,0,0,2,2,2,1,2,1,1,1],[2,2,2,0,1,0,1,2,1,2,0,1,1,0,1,0,1,0,1,1,2,0,1,0,2,0,0,1,2,1,2,1,0,1,1,1,1,0,1,2,1,2,0,0,0,1,1,0,2,0,0,2,1,2,0,2,2,2,2,1,2,2,1,1,2,1,0,1,0,0,1,2,0,1,0,0,2,1,2,1,2,1,0,2,2,0,0,2,1,0,2,0,2,0,1,2,0,0,2,0,0,0,1,0,2,1,2,0,2,0,0,2,0,1,2,1,1,1,1,2,0,1,1,2,0,1,0,0,2,0,0,2,1],[0,2,0,2,1,0,2,2,1,2,1,0,1,0,2,2,0,1,2,0,2,0,1,1,1,1,1,0,2,2,0,1,0,1,0,1,0,2,2,2,2,2,2,0,1,0,2,2,0,0,1,0,1,2,0,2,2,1,2,0,2,2,1,2,0,1,1,2,1,2,2,0,2,0,0,1,1,1,1,0,2,1,2,1,0,1,2,0,1,0,1,1,0,1,2,2,0,1,1,2,1,0,2,2,2,1,1,2,2,2,2,0,0,1,0,0,0,0,1,0,2,2,2,1,2,0,0,1,1,0,0,2,1],[0,1,1,0,1,2,2,0,0,0,1,0,2,2,0,2,1,2,0,1,1,1,0,0,1,2,1,0,0,2,1,2,1,1,0,2,0,2,2,0,2,2,1,2,0,1,0,0,1,2,0,0,0,1,1,2,1,1,0,1,2,2,0,1,0,0,0,1,0,1,1,0,1,2,0,0,1,1,1,2,0,2,1,0,2,2,1,0,2,0,1,0,2,1,2,0,2,0,2,2,1,0,0,1,0,1,2,1,2,2,0,1,0,2,2,1,1,2,0,2,2,2,0,2,0,0,2,1,2,2,1,2,1],[0,1,1,1,2,1,1,2,2,2,1,0,2,1,2,0,1,1,2,2,2,0,0,2,2,1,0,0,1,1,0,0,0,2,1,0,0,0,0,2,1,2,0,2,1,1,1,0,0,1,1,1,0,1,1,2,2,2,2,2,0,2,1,1,0,2,0,1,2,0,0,0,2,0,1,0,0,1,2,2,1,0,2,1,2,1,0,1,0,2,2,0,2,0,1,1,2,0,0,2,2,1,0,0,1,1,1,0,1,0,0,0,0,1,0,0,2,1,0,0,1,1,1,0,0,1,0,0,2,1,1,1,0],[1,1,2,0,1,2,1,1,0,1,2,0,2,2,0,1,1,1,0,2,1,1,1,2,2,1,1,2,2,0,2,0,1,0,1,0,1,0,0,1,1,0,0,2,0,0,2,1,2,2,1,0,2,1,0,2,2,0,0,0,1,1,2,1,1,2,0,1,0,1,0,1,1,1,1,1,1,1,0,2,1,1,1,2,1,2,2,2,0,0,1,1,0,0,2,2,0,1,0,1,1,1,0,2,1,0,2,1,0,2,2,1,2,0,0,0,2,2,1,0,0,0,0,2,0,2,1,0,2,0,1,0,0],[2,0,0,2,2,2,0,0,1,0,1,1,0,1,1,0,0,1,1,2,1,0,0,2,2,2,2,1,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,1,2,2,1,0,0,2,0,1,1,2,1,0,2,1,0,0,1,2,0,0,0,1,0,2,0,1,0,2,2,0,1,1,2,2,1,1,1,1,2,1,2,2,2,0,2,2,2,0,1,0,1,1,1,0,0,1,2,0,2,0,1,1,2,2,1,2,2,0,0,0,0,1,0,0,2,1,2,2,2,1,2,1,1,1,2,2,2,0,2],[2,0,1,1,0,0,1,1,0,1,0,1,0,0,2,2,0,2,0,0,0,0,2,2,0,1,1,0,0,2,0,2,0,2,2,0,0,1,0,0,0,1,2,1,1,0,0,2,1,1,0,1,0,0,1,1,1,0,1,1,1,0,2,0,2,2,0,1,2,0,1,0,2,2,1,2,2,1,2,1,2,2,2,0,0,0,1,1,0,0,1,0,1,0,2,0,0,0,0,0,1,0,0,0,2,2,1,2,0,0,2,0,1,2,2,2,0,1,0,1,0,1,0,0,0,0,0,2,1,0,1,0,1],[1,0,0,0,0,2,1,1,1,1,1,0,1,2,2,2,2,1,0,2,2,2,1,2,2,2,0,1,2,0,1,0,1,1,2,2,2,0,1,1,2,0,2,2,1,1,0,2,2,1,1,1,2,1,1,2,1,2,1,2,2,1,0,1,2,2,2,0,2,2,2,2,0,2,1,1,2,2,1,0,2,1,1,2,2,1,0,2,1,1,1,2,0,0,0,0,0,2,1,0,0,2,1,0,2,0,0,1,2,0,1,0,2,1,1,2,0,2,0,2,0,0,0,2,2,1,1,2,1,2,1,0,0],[2,1,2,0,2,2,2,1,1,2,2,0,1,1,1,2,0,1,0,2,2,1,0,0,2,1,2,1,1,0,0,2,0,2,0,1,0,2,0,1,0,2,2,2,2,0,1,1,2,0,2,0,0,1,2,0,0,0,2,2,2,0,0,1,0,0,0,0,2,0,2,1,2,1,0,0,1,0,1,0,1,2,0,0,1,0,1,1,2,2,1,1,2,0,1,2,2,1,1,1,2,2,1,1,1,1,1,0,1,0,1,1,0,2,0,0,1,1,0,1,0,2,1,2,0,0,2,2,0,1,1,2,2],[0,2,1,1,0,1,2,1,0,0,2,0,2,2,2,1,0,1,2,1,0,1,2,0,0,0,0,2,0,1,0,2,1,0,2,1,2,2,2,1,2,0,0,0,1,0,2,1,1,2,1,1,0,2,0,0,1,0,0,1,0,2,2,1,0,1,2,1,1,2,0,1,0,0,0,0,1,1,0,0,1,2,0,1,1,0,2,0,1,2,1,1,0,1,1,0,0,1,2,1,0,1,0,0,1,1,0,0,2,0,0,2,1,0,1,0,0,1,0,1,0,2,2,2,1,0,2,0,2,1,0,0,0],[2,2,2,0,2,0,1,0,2,1,0,1,0,2,0,1,0,0,2,0,2,2,1,0,0,0,0,1,0,1,2,2,0,0,0,0,0,0,1,0,1,0,1,1,2,2,0,1,1,1,1,2,0,0,2,1,0,2,0,2,0,0,2,1,0,2,2,0,2,2,0,1,1,0,0,1,1,1,0,0,1,0,0,0,0,2,1,0,1,1,0,1,0,1,0,0,1,1,1,1,2,2,1,2,2,1,1,1,2,0,2,1,1,0,0,0,1,2,1,0,1,2,0,0,2,0,2,0,0,1,1,0,0],[1,1,2,0,1,2,2,1,2,2,2,0,1,1,0,1,1,1,2,1,1,1,0,1,0,2,2,0,1,0,2,0,1,0,2,2,0,0,0,0,0,1,0,1,2,2,0,2,1,0,2,2,0,2,1,0,1,0,1,1,0,2,2,2,0,1,0,0,0,2,0,2,2,1,0,1,0,1,1,2,0,1,0,2,0,0,2,1,0,0,2,2,2,1,1,0,1,0,1,1,0,1,2,0,2,2,0,2,0,2,2,2,2,1,0,1,1,0,0,2,2,1,0,2,0,1,0,0,2,2,2,0,2],[1,0,1,0,2,1,0,1,2,0,0,2,1,1,1,1,1,1,1,0,2,0,2,1,0,0,0,2,0,1,0,2,0,1,1,2,2,2,2,0,2,0,2,1,0,2,2,0,1,2,2,2,1,1,1,0,2,1,0,1,0,2,1,1,1,1,0,0,1,0,0,1,1,2,1,0,2,0,1,0,0,0,1,2,1,0,2,2,1,2,0,0,2,0,1,1,1,2,2,0,1,1,2,0,2,0,1,0,0,1,0,2,0,2,1,0,1,2,0,1,2,0,1,1,0,0,0,0,1,0,2,0,0]]";
        System.out.println(new Solution10().minimumVisitedCells(Utils.createTwoDimensionArrayFromString(data)));
    }

    /**
     * 先来个暴力法，试试思路
     */
    public int minimumVisitedCells(int[][] grid) {

        //if valid
        int height = grid.length;
        int width = grid[0].length;

        //dp[i][j]代表从 i,j移动到终点位置的最少移动格子数
        int[][] dp = new int[height][width];

        //this in end, of course is 1
        dp[height - 1][width - 1] = 1;

        //bfs
        moveFromPoint(grid, dp, height - 1, width - 1);

        return dp[0][0] == 0 ? -1 : dp[0][0];
    }


    public void moveFromPoint(int[][] grid, int[][] dp, int i, int j) {
        //向上移动
        Queue<int[]> queue = new ArrayDeque<>();
        for (int k = i - 1; k >= 0; k--) {
            //可达分析
            if (grid[k][j] >= i - k) {
                if (dp[k][j] <= 0) {
                    //之前不可达 变为可达
                    dp[k][j] = dp[i][j] + 1;
                    //记录可达的坐标，加入队列，准备递归
                    queue.offer(new int[]{k, j});
                } else if (dp[k][j] > dp[i][j] + 1) {
                    //之前可达，变更最小可达距离
                    dp[k][j] = dp[i][j] + 1;
                    queue.offer(new int[]{k, j});
                }
            } else {
                dp[k][j] = Math.max(dp[k][j], 0);
            }
        }

        //向左移动
        for (int k = j - 1; k >= 0; k--) {
            if (grid[i][k] >= j - k) {
                if (dp[i][k] <= 0) {
                    dp[i][k] = dp[i][j] + 1;
                    queue.offer(new int[]{i, k});
                } else if (dp[i][k] > dp[i][j] + 1) {
                    dp[i][k] = dp[i][j] + 1;
                    queue.offer(new int[]{i, k});
                }
            } else {
                dp[i][k] = Math.max(dp[i][k], 0);
            }
        }

        if (dp[0][0] > 0 && dp[0][0] < dp[i][j]) {
            //提前剪了这条路
            return;
        }

        //遍历队列，递归
        for (int[] ints : queue) {
            moveFromPoint(grid, dp, ints[0], ints[1]);
        }
    }
}
